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;
  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;
  }
  