#include <bits/stdc++.h>
using namespace std;
struct node {
  int x, y, c;
  bool operator<(const node &t) const { return x < t.x; }
};
node st[100000 + 1];
bool cmp(node a, node b) { return a.y < b.y; }
int n, ans, k1[100000 + 1], k2[100000 + 1], length1, length2;
struct bit {
  int c[100000 + 1];
  void clear() {
    for (int i = 1; i <= n; ++i) c[i] = 0;
    return;
  }
  int lowbit(int x) { return x & (-x); }
  void add(int x, int d) {
    for (; x <= n; x += lowbit(x)) c[x] += d;
    return;
  }
  int Sum(int x) {
    int res = 0;
    for (; x >= 1; x -= lowbit(x)) res += c[x];
    return res;
  }
  int query(int l, int r) { return Sum(r) - Sum(l - 1); }
};
bit T1[3], T2[3];
int Query1(int c1, int c2) {
  int x = 0;
  for (int i = log(n) / log(2); i >= 0; --i)
    if (x + (1 << i) <= n - 1 &&
        T1[c1].Sum(x + (1 << i)) <= T1[c2].query(x + (1 << i) + 1, n))
      x += (1 << i);
  return max(T1[c1].Sum(x), T1[c2].query(x + 2, n));
}
int Query2(int c1, int c2) {
  int x = 0;
  for (int i = log(n) / log(2); i >= 0; --i)
    if (x + (1 << i) <= n - 1 &&
        T2[c1].Sum(x + (1 << i)) <= T2[c2].query(x + (1 << i) + 1, n))
      x += (1 << i);
  return max(T2[c1].Sum(x), T2[c2].query(x + 2, n));
}
int read() {
  char c = 0;
  int sum = 0, f = 1;
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') c = getchar(), f = -1;
  while ('0' <= c && c <= '9') sum = sum * 10 + c - '0', c = getchar();
  return sum * f;
}
void solveA() {
  for (int i = 0; i <= 2; ++i) T1[i].clear(), T2[i].clear();
  for (int i = 1; i <= n; ++i) T2[st[i].c].add(st[i].y, 1);
  int ps = 0;
  for (int i = 1; i <= length1; ++i) {
    while (ps + 1 <= n && st[ps + 1].x <= i)
      ps++, T1[st[ps].c].add(st[ps].y, 1), T2[st[ps].c].add(st[ps].y, -1);
    ans = max(ans, min(max(Query1(0, 1), Query1(1, 0)), T2[2].Sum(n)));
    ans = max(ans, min(max(Query1(0, 2), Query1(2, 0)), T2[1].Sum(n)));
    ans = max(ans, min(max(Query1(1, 2), Query1(2, 1)), T2[0].Sum(n)));
    ans = max(ans, min(max(Query2(0, 1), Query2(1, 0)), T1[2].Sum(n)));
    ans = max(ans, min(max(Query2(0, 2), Query2(2, 0)), T1[1].Sum(n)));
    ans = max(ans, min(max(Query2(1, 2), Query2(2, 1)), T1[0].Sum(n)));
  }
  return;
}
void solveB() {
  for (int i = 0; i <= 2; ++i) T1[i].clear(), T2[i].clear();
  for (int i = 1; i <= n; ++i) T2[st[i].c].add(st[i].x, 1);
  int ps = 0;
  for (int i = 1; i <= length1; ++i) {
    while (ps + 1 <= n && st[ps + 1].x <= i)
      ps++, T1[st[ps].c].add(st[ps].x, 1), T2[st[ps].c].add(st[ps].x, -1);
    ans = max(ans, min(max(Query1(0, 1), Query1(1, 0)), T2[2].Sum(n)));
    ans = max(ans, min(max(Query1(0, 2), Query1(2, 0)), T2[1].Sum(n)));
    ans = max(ans, min(max(Query1(1, 2), Query1(2, 1)), T2[0].Sum(n)));
    ans = max(ans, min(max(Query2(0, 1), Query2(1, 0)), T1[2].Sum(n)));
    ans = max(ans, min(max(Query2(0, 2), Query2(2, 0)), T1[1].Sum(n)));
    ans = max(ans, min(max(Query2(1, 2), Query2(2, 1)), T1[0].Sum(n)));
  }
  return;
}
void solveC() {
  for (int i = 0; i <= 2; ++i) T1[i].clear(), T2[i].clear();
  for (int i = 1; i <= n; ++i) T2[st[i].c].add(st[i].x, 1);
  int ps = 0;
  for (int i = 1; i <= length2; ++i) {
    while (ps + 1 <= n && st[ps + 1].y <= i)
      ps++, T1[st[ps].c].add(st[ps].x, 1), T2[st[ps].c].add(st[ps].x, -1);
    ans = max(ans, min(max(Query1(0, 1), Query1(1, 0)), T2[2].Sum(n)));
    ans = max(ans, min(max(Query1(0, 2), Query1(2, 0)), T2[1].Sum(n)));
    ans = max(ans, min(max(Query1(1, 2), Query1(2, 1)), T2[0].Sum(n)));
    ans = max(ans, min(max(Query2(0, 1), Query2(1, 0)), T1[2].Sum(n)));
    ans = max(ans, min(max(Query2(0, 2), Query2(2, 0)), T1[1].Sum(n)));
    ans = max(ans, min(max(Query2(1, 2), Query2(2, 1)), T1[0].Sum(n)));
  }
  return;
}
void solveD() {
  for (int i = 0; i <= 2; ++i) T1[i].clear(), T2[i].clear();
  for (int i = 1; i <= n; ++i) T2[st[i].c].add(st[i].y, 1);
  int ps = 0;
  for (int i = 1; i <= length2; ++i) {
    while (ps + 1 <= n && st[ps + 1].y <= i)
      ps++, T1[st[ps].c].add(st[ps].y, 1), T2[st[ps].c].add(st[ps].y, -1);
    ans = max(ans, min(max(Query1(0, 1), Query1(1, 0)), T2[2].Sum(n)));
    ans = max(ans, min(max(Query1(0, 2), Query1(2, 0)), T2[1].Sum(n)));
    ans = max(ans, min(max(Query1(1, 2), Query1(2, 1)), T2[0].Sum(n)));
    ans = max(ans, min(max(Query2(0, 1), Query2(1, 0)), T1[2].Sum(n)));
    ans = max(ans, min(max(Query2(0, 2), Query2(2, 0)), T1[1].Sum(n)));
    ans = max(ans, min(max(Query2(1, 2), Query2(2, 1)), T1[0].Sum(n)));
  }
  return;
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i)
    st[i].x = read(), st[i].y = read(), st[i].c = read() - 1,
    k1[++length1] = st[i].x, k2[++length2] = st[i].y;
  sort(k1 + 1, k1 + length1 + 1),
      length1 = unique(k1 + 1, k1 + length1 + 1) - k1 - 1;
  sort(k2 + 1, k2 + length2 + 1),
      length2 = unique(k2 + 1, k2 + length2 + 1) - k2 - 1;
  for (int i = 1; i <= n; ++i)
    st[i].x = lower_bound(k1 + 1, k1 + length1 + 1, st[i].x) - k1,
    st[i].y = lower_bound(k2 + 1, k2 + length2 + 1, st[i].y) - k2;
  sort(st + 1, st + n + 1), solveA(), solveB(), sort(st + 1, st + n + 1, cmp),
      solveC(), solveD();
  printf("%d\n", ans * 3);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

On an endless checkered sheet of paper, n cells are chosen and colored in three colors, where n is divisible by 3. It turns out that there are exactly n/3 marked cells of each of three colors! 

Find the largest such k that it's possible to choose k/3 cells of each color, remove all other marked cells, and then select three rectangles with sides parallel to the grid lines so that the following conditions hold:

  * No two rectangles can intersect (but they can share a part of the boundary). In other words, the area of intersection of any two of these rectangles must be 0.
  * The i-th rectangle contains all the chosen cells of the i-th color and no chosen cells of other colors, for i = 1, 2, 3. 

Input

The first line of the input contains a single integer n — the number of the marked cells (3 ≤ n ≤ 10^5, n is divisible by 3).

The i-th of the following n lines contains three integers x_i, y_i, c_i (|x_i|,|y_i| ≤ 10^9; 1 ≤ c_i ≤ 3), where (x_i, y_i) are the coordinates of the i-th marked cell and c_i is its color.

It's guaranteed that all cells (x_i, y_i) in the input are distinct, and that there are exactly n/3 cells of each color.

Output

Output a single integer k — the largest number of cells you can leave.

Examples

Input


9
2 3 1
4 1 2
2 1 3
3 4 1
5 3 2
4 4 3
2 4 1
5 2 2
3 5 3


Output


6


Input


3
1 1 1
2 2 2
3 3 3


Output


3

Note

In the first sample, it's possible to leave 6 cells with indexes 1, 5, 6, 7, 8, 9.

In the second sample, it's possible to leave 3 cells with indexes 1, 2, 3.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct node {
  int x, y, c;
  bool operator<(const node &t) const { return x < t.x; }
};
node st[100000 + 1];
bool cmp(node a, node b) { return a.y < b.y; }
int n, ans, k1[100000 + 1], k2[100000 + 1], length1, length2;
struct bit {
  int c[100000 + 1];
  void clear() {
    for (int i = 1; i <= n; ++i) c[i] = 0;
    return;
  }
  int lowbit(int x) { return x & (-x); }
  void add(int x, int d) {
    for (; x <= n; x += lowbit(x)) c[x] += d;
    return;
  }
  int Sum(int x) {
    int res = 0;
    for (; x >= 1; x -= lowbit(x)) res += c[x];
    return res;
  }
  int query(int l, int r) { return Sum(r) - Sum(l - 1); }
};
bit T1[3], T2[3];
int Query1(int c1, int c2) {
  int x = 0;
  for (int i = log(n) / log(2); i >= 0; --i)
    if (x + (1 << i) <= n - 1 &&
        T1[c1].Sum(x + (1 << i)) <= T1[c2].query(x + (1 << i) + 1, n))
      x += (1 << i);
  return max(T1[c1].Sum(x), T1[c2].query(x + 2, n));
}
int Query2(int c1, int c2) {
  int x = 0;
  for (int i = log(n) / log(2); i >= 0; --i)
    if (x + (1 << i) <= n - 1 &&
        T2[c1].Sum(x + (1 << i)) <= T2[c2].query(x + (1 << i) + 1, n))
      x += (1 << i);
  return max(T2[c1].Sum(x), T2[c2].query(x + 2, n));
}
int read() {
  char c = 0;
  int sum = 0, f = 1;
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') c = getchar(), f = -1;
  while ('0' <= c && c <= '9') sum = sum * 10 + c - '0', c = getchar();
  return sum * f;
}
void solveA() {
  for (int i = 0; i <= 2; ++i) T1[i].clear(), T2[i].clear();
  for (int i = 1; i <= n; ++i) T2[st[i].c].add(st[i].y, 1);
  int ps = 0;
  for (int i = 1; i <= length1; ++i) {
    while (ps + 1 <= n && st[ps + 1].x <= i)
      ps++, T1[st[ps].c].add(st[ps].y, 1), T2[st[ps].c].add(st[ps].y, -1);
    ans = max(ans, min(max(Query1(0, 1), Query1(1, 0)), T2[2].Sum(n)));
    ans = max(ans, min(max(Query1(0, 2), Query1(2, 0)), T2[1].Sum(n)));
    ans = max(ans, min(max(Query1(1, 2), Query1(2, 1)), T2[0].Sum(n)));
    ans = max(ans, min(max(Query2(0, 1), Query2(1, 0)), T1[2].Sum(n)));
    ans = max(ans, min(max(Query2(0, 2), Query2(2, 0)), T1[1].Sum(n)));
    ans = max(ans, min(max(Query2(1, 2), Query2(2, 1)), T1[0].Sum(n)));
  }
  return;
}
void solveB() {
  for (int i = 0; i <= 2; ++i) T1[i].clear(), T2[i].clear();
  for (int i = 1; i <= n; ++i) T2[st[i].c].add(st[i].x, 1);
  int ps = 0;
  for (int i = 1; i <= length1; ++i) {
    while (ps + 1 <= n && st[ps + 1].x <= i)
      ps++, T1[st[ps].c].add(st[ps].x, 1), T2[st[ps].c].add(st[ps].x, -1);
    ans = max(ans, min(max(Query1(0, 1), Query1(1, 0)), T2[2].Sum(n)));
    ans = max(ans, min(max(Query1(0, 2), Query1(2, 0)), T2[1].Sum(n)));
    ans = max(ans, min(max(Query1(1, 2), Query1(2, 1)), T2[0].Sum(n)));
    ans = max(ans, min(max(Query2(0, 1), Query2(1, 0)), T1[2].Sum(n)));
    ans = max(ans, min(max(Query2(0, 2), Query2(2, 0)), T1[1].Sum(n)));
    ans = max(ans, min(max(Query2(1, 2), Query2(2, 1)), T1[0].Sum(n)));
  }
  return;
}
void solveC() {
  for (int i = 0; i <= 2; ++i) T1[i].clear(), T2[i].clear();
  for (int i = 1; i <= n; ++i) T2[st[i].c].add(st[i].x, 1);
  int ps = 0;
  for (int i = 1; i <= length2; ++i) {
    while (ps + 1 <= n && st[ps + 1].y <= i)
      ps++, T1[st[ps].c].add(st[ps].x, 1), T2[st[ps].c].add(st[ps].x, -1);
    ans = max(ans, min(max(Query1(0, 1), Query1(1, 0)), T2[2].Sum(n)));
    ans = max(ans, min(max(Query1(0, 2), Query1(2, 0)), T2[1].Sum(n)));
    ans = max(ans, min(max(Query1(1, 2), Query1(2, 1)), T2[0].Sum(n)));
    ans = max(ans, min(max(Query2(0, 1), Query2(1, 0)), T1[2].Sum(n)));
    ans = max(ans, min(max(Query2(0, 2), Query2(2, 0)), T1[1].Sum(n)));
    ans = max(ans, min(max(Query2(1, 2), Query2(2, 1)), T1[0].Sum(n)));
  }
  return;
}
void solveD() {
  for (int i = 0; i <= 2; ++i) T1[i].clear(), T2[i].clear();
  for (int i = 1; i <= n; ++i) T2[st[i].c].add(st[i].y, 1);
  int ps = 0;
  for (int i = 1; i <= length2; ++i) {
    while (ps + 1 <= n && st[ps + 1].y <= i)
      ps++, T1[st[ps].c].add(st[ps].y, 1), T2[st[ps].c].add(st[ps].y, -1);
    ans = max(ans, min(max(Query1(0, 1), Query1(1, 0)), T2[2].Sum(n)));
    ans = max(ans, min(max(Query1(0, 2), Query1(2, 0)), T2[1].Sum(n)));
    ans = max(ans, min(max(Query1(1, 2), Query1(2, 1)), T2[0].Sum(n)));
    ans = max(ans, min(max(Query2(0, 1), Query2(1, 0)), T1[2].Sum(n)));
    ans = max(ans, min(max(Query2(0, 2), Query2(2, 0)), T1[1].Sum(n)));
    ans = max(ans, min(max(Query2(1, 2), Query2(2, 1)), T1[0].Sum(n)));
  }
  return;
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i)
    st[i].x = read(), st[i].y = read(), st[i].c = read() - 1,
    k1[++length1] = st[i].x, k2[++length2] = st[i].y;
  sort(k1 + 1, k1 + length1 + 1),
      length1 = unique(k1 + 1, k1 + length1 + 1) - k1 - 1;
  sort(k2 + 1, k2 + length2 + 1),
      length2 = unique(k2 + 1, k2 + length2 + 1) - k2 - 1;
  for (int i = 1; i <= n; ++i)
    st[i].x = lower_bound(k1 + 1, k1 + length1 + 1, st[i].x) - k1,
    st[i].y = lower_bound(k2 + 1, k2 + length2 + 1, st[i].y) - k2;
  sort(st + 1, st + n + 1), solveA(), solveB(), sort(st + 1, st + n + 1, cmp),
      solveC(), solveD();
  printf("%d\n", ans * 3);
  return 0;
}

```