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

### Prompt

Your task is to create a cpp solution to 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;
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;
}

```