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;
  int n, X[100005], Y[100005], C[100005];
  int ax[100005], ay[100005], ix, iy;
  struct Nod {
    int x, y, c;
    Nod(int _x = 0, int _y = 0, int _c = 0) : x(_x), y(_y), c(_c) {}
  } dx[100005], dy[100005];
  inline bool cmpx(const Nod &a, const Nod &b) { return a.x < b.x; }
  inline bool cmpy(const Nod &a, const Nod &b) { return a.y < b.y; }
  int getx(int i, int x, int v) {
    while (i && i <= n && dx[i].x == x) i += v;
    return i > n ? 0 : i;
  }
  int prex(int st, int c, int k) {
    if (!st) return 0;
    for (int i = st; i >= 1; --i)
      if (dx[i].c == c) {
        if (!(--k)) return i;
      }
    return 0;
  }
  int nxtx(int st, int c, int k) {
    if (!st) return 0;
    for (int i = st; i <= n; ++i)
      if (dx[i].c == c) {
        if (!(--k)) return i;
      }
    return 0;
  }
  int gety(int i, int y, int v) {
    while (i && i <= n && dy[i].y == y) i += v;
    return i > n ? 0 : i;
  }
  int prey(int st, int c, int k) {
    if (!st) return 0;
    for (int i = st; i >= 1; --i)
      if (dy[i].c == c) {
        if (!(--k)) return i;
      }
    return 0;
  }
  int nxty(int st, int c, int k) {
    if (!st) return 0;
    for (int i = st; i <= n; ++i)
      if (dy[i].c == c) {
        if (!(--k)) return i;
      }
    return 0;
  }
  bool Judge(int c1, int c2, int c3, int k) {
    int p, lft, lx, ly;
    p = 1;
    p = nxtx(p, c1, k);
    p = getx(p, dx[p].x, 1);
    p = nxtx(p, c2, k);
    p = getx(p, dx[p].x, 1);
    p = nxtx(p, c3, k);
    if (p) return true;
    p = 1;
    p = nxty(p, c1, k);
    p = gety(p, dy[p].y, 1);
    p = nxty(p, c2, k);
    p = gety(p, dy[p].y, 1);
    p = nxty(p, c3, k);
    if (p) return true;
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dx[i].c == c1) {
        if (!(--lft)) {
          lx = dx[i].x;
          break;
        }
      }
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dy[i].c == c2 && dy[i].x > lx) {
        if (!(--lft)) {
          ly = dy[i].y;
          break;
        }
      }
    if (!lft) {
      lft = k;
      for (int i = 1; i <= n; ++i)
        if (dy[i].c == c3 && dy[i].x > lx && dy[i].y > ly) {
          if (!(--lft)) break;
        }
      if (!lft) return true;
    }
    lft = k;
    for (int i = n; i >= 1; --i)
      if (dx[i].c == c1) {
        if (!(--lft)) {
          lx = dx[i].x;
          break;
        }
      }
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dy[i].c == c2 && dy[i].x < lx) {
        if (!(--lft)) {
          ly = dy[i].y;
          break;
        }
      }
    if (!lft) {
      lft = k;
      for (int i = 1; i <= n; ++i)
        if (dy[i].c == c3 && dy[i].x < lx && dy[i].y > ly) {
          if (!(--lft)) break;
        }
      if (!lft) return true;
    }
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dy[i].c == c1) {
        if (!(--lft)) {
          ly = dy[i].y;
          break;
        }
      }
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dx[i].c == c2 && dx[i].y > ly) {
        if (!(--lft)) {
          lx = dx[i].x;
          break;
        }
      }
    if (!lft) {
      lft = k;
      for (int i = 1; i <= n; ++i)
        if (dx[i].c == c3 && dx[i].x > lx && dx[i].y > ly) {
          if (!(--lft)) break;
        }
      if (!lft) return true;
    }
    lft = k;
    for (int i = n; i >= 1; --i)
      if (dy[i].c == c1) {
        if (!(--lft)) {
          ly = dy[i].y;
          break;
        }
      }
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dx[i].c == c2 && dx[i].y < ly) {
        if (!(--lft)) {
          lx = dx[i].x;
          break;
        }
      }
    if (!lft) {
      lft = k;
      for (int i = 1; i <= n; ++i)
        if (dx[i].c == c3 && dx[i].x > lx && dx[i].y < ly) {
          if (!(--lft)) break;
        }
      if (!lft) return true;
    }
    return false;
  }
  bool check(int k) {
    int p[3] = {1, 2, 3};
    do {
      if (Judge(p[0], p[1], p[2], k)) return true;
    } while (next_permutation(p, p + 3));
    return false;
  }
  int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
      cin >> X[i] >> Y[i] >> C[i];
      ax[++ix] = X[i];
      ay[++iy] = Y[i];
    }
    sort(ax + 1, ax + ix + 1);
    ix = unique(ax + 1, ax + ix + 1) - ax - 1;
    sort(ay + 1, ay + iy + 1);
    iy = unique(ay + 1, ay + iy + 1) - ay - 1;
    for (int i = 1; i <= n; ++i) {
      int x = lower_bound(ax + 1, ax + ix + 1, X[i]) - ax;
      int y = lower_bound(ay + 1, ay + iy + 1, Y[i]) - ay;
      dx[i] = Nod(x, y, C[i]);
      dy[i] = Nod(x, y, C[i]);
    }
    sort(dx + 1, dx + n + 1, cmpx);
    sort(dy + 1, dy + n + 1, cmpy);
    int l = 1, r = n / 3, mid;
    while (l < r) {
      mid = (l + r + 1) >> 1;
      if (check(mid))
        l = mid;
      else
        r = mid - 1;
    }
    cout << l * 3 << endl;
    return 0;
  }
  