description: 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.
solution: #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;
  }
  