#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template <class T>
bool ckmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool ckmax(T &a, const T &b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}
const int INFi = 2e9;
const ll INF = 2e18;
const int maxN = 2e5;
const int LG = 30;
struct fenwick {
  int n{};
  vector<ll> fenw{};
  void build(int k) {
    n = k;
    fenw.resize(n);
  }
  void upd(int i, ll x) {
    for (; i < n; i = i | (i + 1)) fenw[i] += x;
  }
  ll get(int i) {
    ll res = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1) res += fenw[i];
    return res;
  }
};
int lower_bound(fenwick &f1, fenwick &f2) {
  int r = -1;
  ll x = f2.get(f2.n - 1);
  for (int j = 20; j >= 0; --j) {
    int t = (1 << j);
    if (r + t >= f1.n) continue;
    if (f2.fenw[r + t] + f1.fenw[r + t] >= x) continue;
    r += t;
    x -= f2.fenw[r] + f1.fenw[r];
  }
  return r + 1;
}
void solve() {
  int n;
  cin >> n;
  vector<array<int, 3>> a(n);
  for (int i = 0; i < (n); ++i)
    for (int j = 0; j < (3); ++j) cin >> a[i][j];
  vector<int> xx, yy;
  for (int i = 0; i < (n); ++i) {
    xx.push_back(a[i][0]);
    yy.push_back(a[i][1]);
    a[i][2]--;
  }
  sort((xx).begin(), (xx).end());
  sort((yy).begin(), (yy).end());
  xx.resize(unique((xx).begin(), (xx).end()) - xx.begin());
  yy.resize(unique((yy).begin(), (yy).end()) - yy.begin());
  for (int i = 0; i < (n); ++i) {
    a[i][0] = lower_bound((xx).begin(), (xx).end(), a[i][0]) - xx.begin();
    a[i][1] = lower_bound((yy).begin(), (yy).end(), a[i][1]) - yy.begin();
  }
  int ans = 0;
  for (int _ = 0; _ < (2); ++_) {
    sort((a).begin(), (a).end());
    for (int __ = 0; __ < (2); ++__) {
      vector<fenwick> ct(3);
      for (int i = 0; i < (3); ++i) ct[i].build(n);
      for (int i = 0; i < (n - 1); ++i) {
        auto [x, y, c] = a[i];
        ct[c].upd(y, 1);
        if (a[i + 1][0] == x) continue;
        for (int colR = 0; colR < (3); ++colR) {
          for (int colD = 0; colD < (3); ++colD) {
            if (colD == colR) continue;
            int colU = 3 ^ (colD ^ colR);
            int ctR = n / 3 - ct[colR].get(n - 1);
            int j = lower_bound(ct[colD], ct[colU]);
            for (int k = j - 3; k <= j + 3; ++k) {
              if (k <= 0 || k > n) continue;
              int ctD = ct[colD].get(k - 1);
              int ctU = ct[colU].get(n - 1) - ct[colU].get(k - 1);
              ans = max(ans, min({ctD, ctU, ctR}));
            }
          }
        }
      }
      reverse((a).begin(), (a).end());
    }
    for (int colL = 0; colL < (3); ++colL) {
      for (int colR = 0; colR < (3); ++colR) {
        if (colL == colR) continue;
        int colMid = (colL ^ colR) ^ 3;
        int cntL = 0, cntR = 0;
        int cntMid = n / 3;
        int L = 0, R = n - 1;
        for (int d = 1; d <= n / 3; ++d) {
          while (cntL < d) {
            do {
              int c = a[L++][2];
              if (c == colL) cntL++;
              if (c == colMid) cntMid--;
            } while (L < n && a[L][0] == a[L - 1][0]);
          }
          while (cntR < d) {
            do {
              int c = a[R--][2];
              if (c == colR) cntR++;
              if (c == colMid) cntMid--;
            } while (R >= 0 && a[R][0] == a[R + 1][0]);
          }
          if (cntMid < d) break;
          ans = max(ans, d);
        }
      }
    }
    for (int i = 0; i < (n); ++i) swap(a[i][0], a[i][1]);
  }
  cout << ans * 3 << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  for (int i = 0; i < (t); ++i) {
    solve();
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template <class T>
bool ckmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool ckmax(T &a, const T &b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}
const int INFi = 2e9;
const ll INF = 2e18;
const int maxN = 2e5;
const int LG = 30;
struct fenwick {
  int n{};
  vector<ll> fenw{};
  void build(int k) {
    n = k;
    fenw.resize(n);
  }
  void upd(int i, ll x) {
    for (; i < n; i = i | (i + 1)) fenw[i] += x;
  }
  ll get(int i) {
    ll res = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1) res += fenw[i];
    return res;
  }
};
int lower_bound(fenwick &f1, fenwick &f2) {
  int r = -1;
  ll x = f2.get(f2.n - 1);
  for (int j = 20; j >= 0; --j) {
    int t = (1 << j);
    if (r + t >= f1.n) continue;
    if (f2.fenw[r + t] + f1.fenw[r + t] >= x) continue;
    r += t;
    x -= f2.fenw[r] + f1.fenw[r];
  }
  return r + 1;
}
void solve() {
  int n;
  cin >> n;
  vector<array<int, 3>> a(n);
  for (int i = 0; i < (n); ++i)
    for (int j = 0; j < (3); ++j) cin >> a[i][j];
  vector<int> xx, yy;
  for (int i = 0; i < (n); ++i) {
    xx.push_back(a[i][0]);
    yy.push_back(a[i][1]);
    a[i][2]--;
  }
  sort((xx).begin(), (xx).end());
  sort((yy).begin(), (yy).end());
  xx.resize(unique((xx).begin(), (xx).end()) - xx.begin());
  yy.resize(unique((yy).begin(), (yy).end()) - yy.begin());
  for (int i = 0; i < (n); ++i) {
    a[i][0] = lower_bound((xx).begin(), (xx).end(), a[i][0]) - xx.begin();
    a[i][1] = lower_bound((yy).begin(), (yy).end(), a[i][1]) - yy.begin();
  }
  int ans = 0;
  for (int _ = 0; _ < (2); ++_) {
    sort((a).begin(), (a).end());
    for (int __ = 0; __ < (2); ++__) {
      vector<fenwick> ct(3);
      for (int i = 0; i < (3); ++i) ct[i].build(n);
      for (int i = 0; i < (n - 1); ++i) {
        auto [x, y, c] = a[i];
        ct[c].upd(y, 1);
        if (a[i + 1][0] == x) continue;
        for (int colR = 0; colR < (3); ++colR) {
          for (int colD = 0; colD < (3); ++colD) {
            if (colD == colR) continue;
            int colU = 3 ^ (colD ^ colR);
            int ctR = n / 3 - ct[colR].get(n - 1);
            int j = lower_bound(ct[colD], ct[colU]);
            for (int k = j - 3; k <= j + 3; ++k) {
              if (k <= 0 || k > n) continue;
              int ctD = ct[colD].get(k - 1);
              int ctU = ct[colU].get(n - 1) - ct[colU].get(k - 1);
              ans = max(ans, min({ctD, ctU, ctR}));
            }
          }
        }
      }
      reverse((a).begin(), (a).end());
    }
    for (int colL = 0; colL < (3); ++colL) {
      for (int colR = 0; colR < (3); ++colR) {
        if (colL == colR) continue;
        int colMid = (colL ^ colR) ^ 3;
        int cntL = 0, cntR = 0;
        int cntMid = n / 3;
        int L = 0, R = n - 1;
        for (int d = 1; d <= n / 3; ++d) {
          while (cntL < d) {
            do {
              int c = a[L++][2];
              if (c == colL) cntL++;
              if (c == colMid) cntMid--;
            } while (L < n && a[L][0] == a[L - 1][0]);
          }
          while (cntR < d) {
            do {
              int c = a[R--][2];
              if (c == colR) cntR++;
              if (c == colMid) cntMid--;
            } while (R >= 0 && a[R][0] == a[R + 1][0]);
          }
          if (cntMid < d) break;
          ans = max(ans, d);
        }
      }
    }
    for (int i = 0; i < (n); ++i) swap(a[i][0], a[i][1]);
  }
  cout << ans * 3 << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  for (int i = 0; i < (t); ++i) {
    solve();
  }
  return 0;
}

```