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;
  template <class>
  struct is_container : false_type {};
  template <class... Ts>
  struct is_container<vector<Ts...>> : true_type {};
  template <class... Ts>
  struct is_container<map<Ts...>> : true_type {};
  template <class... Ts>
  struct is_container<unordered_map<Ts...>> : true_type {};
  template <class... Ts>
  struct is_container<set<Ts...>> : true_type {};
  template <class... Ts>
  struct is_container<unordered_set<Ts...>> : true_type {};
  template <class... Ts>
  struct is_container<multiset<Ts...>> : true_type {};
  template <class... Ts>
  struct is_container<unordered_multiset<Ts...>> : true_type {};
  template <class T, class = typename enable_if<is_container<T>::value>::type>
  ostream& operator<<(ostream& o, T x) {
    int f = 1;
    o << "{";
    for (auto y : x) {
      o << (f ? "" : ", ") << y;
      f = 0;
    }
    return o << "}";
  }
  template <class T, class U>
  ostream& operator<<(ostream& o, pair<T, U> x) {
    return o << "(" << x.first << ", " << x.second << ")";
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> a[3];
    for (int i = 0; i < n; i++) {
      int x, y, c;
      cin >> x >> y >> c;
      a[c - 1].push_back({x, y});
    }
    vector<int> ord_x[3], ord_y[3];
    for (int i : {0, 1, 2}) {
      ord_x[i].resize(n / 3);
      ord_y[i].resize(n / 3);
      iota(ord_x[i].begin(), ord_x[i].end(), 0);
      iota(ord_y[i].begin(), ord_y[i].end(), 0);
      sort(ord_x[i].begin(), ord_x[i].end(),
           [&](int j, int k) { return a[i][j].first < a[i][k].first; });
      sort(ord_y[i].begin(), ord_y[i].end(),
           [&](int j, int k) { return a[i][j].second < a[i][k].second; });
    }
    int sol = 0;
    for (int iter : {0, 1}) {
      int lo = 0, hi = n / 3 + 1;
      while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        bool possible = false;
        int perm[3] = {0, 1, 2};
        do {
          int pos_0 = mid - 1;
          int prev_x = a[perm[0]][ord_x[perm[0]][pos_0]].first;
          int pos_1 = 0;
          while (pos_1 < n / 3 &&
                 a[perm[1]][ord_x[perm[1]][pos_1]].first <= prev_x)
            pos_1++;
          pos_1 += mid - 1;
          if (pos_1 >= n / 3) continue;
          prev_x = a[perm[1]][ord_x[perm[1]][pos_1]].first;
          int pos_2 = 0;
          while (pos_2 < n / 3 &&
                 a[perm[2]][ord_x[perm[2]][pos_2]].first <= prev_x)
            pos_2++;
          pos_2 += mid - 1;
          if (pos_2 >= n / 3) continue;
          possible = true;
        } while (next_permutation(perm, perm + 3));
        do {
          int pos_0 = mid - 1;
          int prev_x = a[perm[0]][ord_x[perm[0]][pos_0]].first;
          int pos_1 = 0, cnt_1 = 0;
          while (pos_1 < n / 3) {
            if (a[perm[1]][ord_y[perm[1]][pos_1]].first > prev_x) cnt_1++;
            if (cnt_1 == mid) break;
            pos_1++;
          }
          if (cnt_1 != mid) continue;
          int bottom_y = a[perm[1]][ord_y[perm[1]][pos_1]].second;
          int pos_2 = n / 3 - 1, cnt_2 = 0;
          while (pos_2 >= 0) {
            if (a[perm[2]][ord_y[perm[2]][pos_2]].first > prev_x) cnt_2++;
            if (cnt_2 == mid) break;
            pos_2--;
          }
          if (cnt_2 != mid) continue;
          int top_y = a[perm[2]][ord_y[perm[2]][pos_2]].second;
          if (bottom_y < top_y) possible = true;
        } while (next_permutation(perm, perm + 3));
        do {
          int pos_0 = n / 3 - mid;
          int prev_x = a[perm[0]][ord_x[perm[0]][pos_0]].first;
          int pos_1 = 0, cnt_1 = 0;
          while (pos_1 < n / 3) {
            if (a[perm[1]][ord_y[perm[1]][pos_1]].first < prev_x) cnt_1++;
            if (cnt_1 == mid) break;
            pos_1++;
          }
          if (cnt_1 != mid) continue;
          int bottom_y = a[perm[1]][ord_y[perm[1]][pos_1]].second;
          int pos_2 = n / 3 - 1, cnt_2 = 0;
          while (pos_2 >= 0) {
            if (a[perm[2]][ord_y[perm[2]][pos_2]].first < prev_x) cnt_2++;
            if (cnt_2 == mid) break;
            pos_2--;
          }
          if (cnt_2 != mid) continue;
          int top_y = a[perm[2]][ord_y[perm[2]][pos_2]].second;
          if (bottom_y < top_y) possible = true;
        } while (next_permutation(perm, perm + 3));
        if (possible)
          lo = mid;
        else
          hi = mid;
      }
      sol = max(sol, lo);
      for (int i : {0, 1, 2}) {
        for (int j = 0; j < n / 3; j++) swap(a[i][j].first, a[i][j].second);
        swap(ord_x[i], ord_y[i]);
      }
    }
    sol *= 3;
    cout << sol << '\n';
    return 0;
  }
  