#include <bits/stdc++.h>
using namespace std;
const int MX = 100100;
int n, n3, num, i, j, best, allx[MX], ally[MX], x[MX], y[MX], z[MX], k[MX],
    pos[3][MX], c[270270][3], order[7][7], col[7];
bool u[7];
void init(int i, int L, int R) {
  for (int j = 0; j < 3; j++) c[i][j] = 0;
  if (L == R) return;
  int mid = (L + R) / 2;
  init(i * 2, L, mid);
  init(i * 2 + 1, mid + 1, R);
}
void add(int i, int L, int R, int pos, int col) {
  while (L != R) {
    ++c[i][col];
    int mid = (L + R) / 2;
    if (pos <= mid) {
      R = mid;
      i = i * 2;
    } else {
      L = mid + 1;
      i = i * 2 + 1;
    }
  }
  ++c[i][col];
}
int fnd(int i, int L, int R, int x, int y, int lft, int rgh) {
  if (L == R) return max(min(lft + c[i][x], rgh), min(lft, rgh + c[i][y]));
  int mid = (L + R) / 2;
  int lv = lft + c[i * 2][x];
  int rv = rgh + c[i * 2 + 1][y];
  if (lv == rv) return rv;
  if (lv > rv) return fnd(i * 2, L, mid, x, y, lft, rv);
  return fnd(i * 2 + 1, mid + 1, R, x, y, lv, rgh);
}
void rot() {
  for (int i = 0; i < n; i++) {
    int tmp = y[i];
    y[i] = n - x[i] + 1;
    x[i] = tmp;
  }
}
bool cmp(int i, int j) { return x[i] < x[j]; }
void rec(int l) {
  if (l == 3) {
    for (int i = 0; i < 3; i++) order[num][i] = col[i];
    num++;
    return;
  }
  for (int i = 0; i < 3; i++)
    if (!u[i]) {
      u[i] = true;
      col[l] = i;
      rec(l + 1);
      u[i] = false;
    }
}
void solve() {
  for (int j = 0; j < 4; j++) {
    sort(k, k + n, cmp);
    init(1, 1, n);
    for (int i = 0; i < n; i++) {
      add(1, 1, n, y[k[i]], z[k[i]]);
      if (i + 1 == n || x[k[i]] != x[k[i + 1]])
        for (int idx = 0; idx < num; idx++) {
          if (n3 - c[1][order[idx][0]] > best)
            best = max(best,
                       min(n3 - c[1][order[idx][0]],
                           fnd(1, 1, n, order[idx][1], order[idx][2], 0, 0)));
        }
    }
    if (j < 3) rot();
  }
}
void binsearch() {
  for (int idx = 0; idx < num; idx++) {
    int le = 0, ri = n3;
    while (le < ri) {
      int mid = (le + ri) / 2 + 1;
      int prv = 0, j, i;
      for (j = 0; j < 3; j++) {
        int cur = order[idx][j];
        for (i = prv + 1; i <= n; i++)
          if (pos[cur][i] - pos[cur][prv] >= mid) break;
        if (i > n) break;
        prv = i;
      }
      if (j >= 3)
        le = mid;
      else
        ri = mid - 1;
    }
    best = max(best, ri);
  }
}
int main() {
  scanf("%d", &n);
  n3 = n / 3;
  for (i = 0; i < n; i++) {
    scanf("%d%d%d", &x[i], &y[i], &z[i]);
    --z[i];
    k[i] = i;
    allx[i] = x[i];
    ally[i] = y[i];
  }
  sort(allx, allx + n);
  sort(ally, ally + n);
  for (i = 0; i < n; i++) {
    x[i] = lower_bound(allx, allx + n, x[i]) - allx + 1;
    y[i] = lower_bound(ally, ally + n, y[i]) - ally + 1;
  }
  rec(0);
  for (j = 0; j < 3; j++)
    for (i = 0; i <= n; i++) pos[j][i] = 0;
  for (i = 0; i < n; i++) ++pos[z[i]][x[i]];
  for (j = 0; j < 3; j++)
    for (i = 1; i <= n; i++) pos[j][i] += pos[j][i - 1];
  binsearch();
  for (j = 0; j < 3; j++)
    for (i = 0; i <= n; i++) pos[j][i] = 0;
  for (i = 0; i < n; i++) ++pos[z[i]][y[i]];
  for (j = 0; j < 3; j++)
    for (i = 1; i <= n; i++) pos[j][i] += pos[j][i - 1];
  binsearch();
  solve();
  printf("%d\n", best * 3);
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

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;
const int MX = 100100;
int n, n3, num, i, j, best, allx[MX], ally[MX], x[MX], y[MX], z[MX], k[MX],
    pos[3][MX], c[270270][3], order[7][7], col[7];
bool u[7];
void init(int i, int L, int R) {
  for (int j = 0; j < 3; j++) c[i][j] = 0;
  if (L == R) return;
  int mid = (L + R) / 2;
  init(i * 2, L, mid);
  init(i * 2 + 1, mid + 1, R);
}
void add(int i, int L, int R, int pos, int col) {
  while (L != R) {
    ++c[i][col];
    int mid = (L + R) / 2;
    if (pos <= mid) {
      R = mid;
      i = i * 2;
    } else {
      L = mid + 1;
      i = i * 2 + 1;
    }
  }
  ++c[i][col];
}
int fnd(int i, int L, int R, int x, int y, int lft, int rgh) {
  if (L == R) return max(min(lft + c[i][x], rgh), min(lft, rgh + c[i][y]));
  int mid = (L + R) / 2;
  int lv = lft + c[i * 2][x];
  int rv = rgh + c[i * 2 + 1][y];
  if (lv == rv) return rv;
  if (lv > rv) return fnd(i * 2, L, mid, x, y, lft, rv);
  return fnd(i * 2 + 1, mid + 1, R, x, y, lv, rgh);
}
void rot() {
  for (int i = 0; i < n; i++) {
    int tmp = y[i];
    y[i] = n - x[i] + 1;
    x[i] = tmp;
  }
}
bool cmp(int i, int j) { return x[i] < x[j]; }
void rec(int l) {
  if (l == 3) {
    for (int i = 0; i < 3; i++) order[num][i] = col[i];
    num++;
    return;
  }
  for (int i = 0; i < 3; i++)
    if (!u[i]) {
      u[i] = true;
      col[l] = i;
      rec(l + 1);
      u[i] = false;
    }
}
void solve() {
  for (int j = 0; j < 4; j++) {
    sort(k, k + n, cmp);
    init(1, 1, n);
    for (int i = 0; i < n; i++) {
      add(1, 1, n, y[k[i]], z[k[i]]);
      if (i + 1 == n || x[k[i]] != x[k[i + 1]])
        for (int idx = 0; idx < num; idx++) {
          if (n3 - c[1][order[idx][0]] > best)
            best = max(best,
                       min(n3 - c[1][order[idx][0]],
                           fnd(1, 1, n, order[idx][1], order[idx][2], 0, 0)));
        }
    }
    if (j < 3) rot();
  }
}
void binsearch() {
  for (int idx = 0; idx < num; idx++) {
    int le = 0, ri = n3;
    while (le < ri) {
      int mid = (le + ri) / 2 + 1;
      int prv = 0, j, i;
      for (j = 0; j < 3; j++) {
        int cur = order[idx][j];
        for (i = prv + 1; i <= n; i++)
          if (pos[cur][i] - pos[cur][prv] >= mid) break;
        if (i > n) break;
        prv = i;
      }
      if (j >= 3)
        le = mid;
      else
        ri = mid - 1;
    }
    best = max(best, ri);
  }
}
int main() {
  scanf("%d", &n);
  n3 = n / 3;
  for (i = 0; i < n; i++) {
    scanf("%d%d%d", &x[i], &y[i], &z[i]);
    --z[i];
    k[i] = i;
    allx[i] = x[i];
    ally[i] = y[i];
  }
  sort(allx, allx + n);
  sort(ally, ally + n);
  for (i = 0; i < n; i++) {
    x[i] = lower_bound(allx, allx + n, x[i]) - allx + 1;
    y[i] = lower_bound(ally, ally + n, y[i]) - ally + 1;
  }
  rec(0);
  for (j = 0; j < 3; j++)
    for (i = 0; i <= n; i++) pos[j][i] = 0;
  for (i = 0; i < n; i++) ++pos[z[i]][x[i]];
  for (j = 0; j < 3; j++)
    for (i = 1; i <= n; i++) pos[j][i] += pos[j][i - 1];
  binsearch();
  for (j = 0; j < 3; j++)
    for (i = 0; i <= n; i++) pos[j][i] = 0;
  for (i = 0; i < n; i++) ++pos[z[i]][y[i]];
  for (j = 0; j < 3; j++)
    for (i = 1; i <= n; i++) pos[j][i] += pos[j][i - 1];
  binsearch();
  solve();
  printf("%d\n", best * 3);
  return 0;
}

```