#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<int, int> > VX[5];
vector<pair<int, int> > VY[5];
int X[101010];
int Y[101010];
int C[101010];
void ref() {
  for (int i = 1; i <= N; i++) swap(X[i], Y[i]);
}
bool f(int m, int a, int b, int c) {
  int x1 = VX[a][m - 1].first + 1;
  int x2 = VX[c][N / 3 - m].first - 1;
  int cnt = 0;
  for (auto& i : VX[b]) {
    if (x1 <= i.first && i.first <= x2) cnt++;
  }
  return cnt >= m;
}
bool g(int m, int a, int b, int c) {
  int y = VY[c][m - 1].second + 1;
  int x;
  int cnt = 0;
  for (auto& i : VX[a]) {
    if (i.second < y) continue;
    cnt++;
    if (cnt >= m) {
      x = i.first + 1;
      break;
    }
  }
  if (cnt < m) return false;
  cnt = 0;
  for (auto& i : VX[b]) {
    if (i.second >= y && i.first >= x) cnt++;
  }
  return cnt >= m;
}
bool h(int m, int a, int b, int c) {
  int y = VY[c][N / 3 - m].second - 1;
  int x;
  int cnt = 0;
  for (auto& i : VX[a]) {
    if (i.second > y) continue;
    cnt++;
    if (cnt >= m) {
      x = i.first + 1;
      break;
    }
  }
  if (cnt < m) return false;
  cnt = 0;
  for (auto& i : VX[b]) {
    if (i.second <= y && i.first >= x) cnt++;
  }
  return cnt >= m;
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d%d%d", &X[i], &Y[i], &C[i]);
  }
  int l = 1, r = N / 3;
  while (l <= r) {
    int m = l + r >> 1;
    bool ok = false;
    for (int z = 0; z < 2; z++) {
      for (int i = 1; i <= 3; i++) {
        VX[i].clear();
        VY[i].clear();
      }
      for (int i = 1; i <= N; i++) {
        VX[C[i]].emplace_back(X[i], Y[i]);
        VY[C[i]].emplace_back(X[i], Y[i]);
      }
      for (int i = 1; i <= 3; i++) {
        sort(VX[i].begin(), VX[i].end());
        sort(VY[i].begin(), VY[i].end(),
             [&](const pair<int, int> a, const pair<int, int> b) {
               return a.second < b.second;
             });
      }
      if (f(m, 1, 2, 3)) {
        ok = true;
        break;
      }
      if (f(m, 1, 3, 2)) {
        ok = true;
        break;
      }
      if (f(m, 2, 1, 3)) {
        ok = true;
        break;
      }
      if (f(m, 2, 3, 1)) {
        ok = true;
        break;
      }
      if (f(m, 3, 1, 2)) {
        ok = true;
        break;
      }
      if (f(m, 3, 2, 1)) {
        ok = true;
        break;
      }
      if (g(m, 1, 2, 3)) {
        ok = true;
        break;
      }
      if (g(m, 1, 3, 2)) {
        ok = true;
        break;
      }
      if (g(m, 2, 1, 3)) {
        ok = true;
        break;
      }
      if (g(m, 2, 3, 1)) {
        ok = true;
        break;
      }
      if (g(m, 3, 1, 2)) {
        ok = true;
        break;
      }
      if (g(m, 3, 2, 1)) {
        ok = true;
        break;
      }
      if (h(m, 1, 2, 3)) {
        ok = true;
        break;
      }
      if (h(m, 1, 3, 2)) {
        ok = true;
        break;
      }
      if (h(m, 2, 1, 3)) {
        ok = true;
        break;
      }
      if (h(m, 2, 3, 1)) {
        ok = true;
        break;
      }
      if (h(m, 3, 1, 2)) {
        ok = true;
        break;
      }
      if (h(m, 3, 2, 1)) {
        ok = true;
        break;
      }
      ref();
    }
    if (ok)
      l = m + 1;
    else
      r = m - 1;
  }
  printf("%d\n", r * 3);
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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;
int N;
vector<pair<int, int> > VX[5];
vector<pair<int, int> > VY[5];
int X[101010];
int Y[101010];
int C[101010];
void ref() {
  for (int i = 1; i <= N; i++) swap(X[i], Y[i]);
}
bool f(int m, int a, int b, int c) {
  int x1 = VX[a][m - 1].first + 1;
  int x2 = VX[c][N / 3 - m].first - 1;
  int cnt = 0;
  for (auto& i : VX[b]) {
    if (x1 <= i.first && i.first <= x2) cnt++;
  }
  return cnt >= m;
}
bool g(int m, int a, int b, int c) {
  int y = VY[c][m - 1].second + 1;
  int x;
  int cnt = 0;
  for (auto& i : VX[a]) {
    if (i.second < y) continue;
    cnt++;
    if (cnt >= m) {
      x = i.first + 1;
      break;
    }
  }
  if (cnt < m) return false;
  cnt = 0;
  for (auto& i : VX[b]) {
    if (i.second >= y && i.first >= x) cnt++;
  }
  return cnt >= m;
}
bool h(int m, int a, int b, int c) {
  int y = VY[c][N / 3 - m].second - 1;
  int x;
  int cnt = 0;
  for (auto& i : VX[a]) {
    if (i.second > y) continue;
    cnt++;
    if (cnt >= m) {
      x = i.first + 1;
      break;
    }
  }
  if (cnt < m) return false;
  cnt = 0;
  for (auto& i : VX[b]) {
    if (i.second <= y && i.first >= x) cnt++;
  }
  return cnt >= m;
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d%d%d", &X[i], &Y[i], &C[i]);
  }
  int l = 1, r = N / 3;
  while (l <= r) {
    int m = l + r >> 1;
    bool ok = false;
    for (int z = 0; z < 2; z++) {
      for (int i = 1; i <= 3; i++) {
        VX[i].clear();
        VY[i].clear();
      }
      for (int i = 1; i <= N; i++) {
        VX[C[i]].emplace_back(X[i], Y[i]);
        VY[C[i]].emplace_back(X[i], Y[i]);
      }
      for (int i = 1; i <= 3; i++) {
        sort(VX[i].begin(), VX[i].end());
        sort(VY[i].begin(), VY[i].end(),
             [&](const pair<int, int> a, const pair<int, int> b) {
               return a.second < b.second;
             });
      }
      if (f(m, 1, 2, 3)) {
        ok = true;
        break;
      }
      if (f(m, 1, 3, 2)) {
        ok = true;
        break;
      }
      if (f(m, 2, 1, 3)) {
        ok = true;
        break;
      }
      if (f(m, 2, 3, 1)) {
        ok = true;
        break;
      }
      if (f(m, 3, 1, 2)) {
        ok = true;
        break;
      }
      if (f(m, 3, 2, 1)) {
        ok = true;
        break;
      }
      if (g(m, 1, 2, 3)) {
        ok = true;
        break;
      }
      if (g(m, 1, 3, 2)) {
        ok = true;
        break;
      }
      if (g(m, 2, 1, 3)) {
        ok = true;
        break;
      }
      if (g(m, 2, 3, 1)) {
        ok = true;
        break;
      }
      if (g(m, 3, 1, 2)) {
        ok = true;
        break;
      }
      if (g(m, 3, 2, 1)) {
        ok = true;
        break;
      }
      if (h(m, 1, 2, 3)) {
        ok = true;
        break;
      }
      if (h(m, 1, 3, 2)) {
        ok = true;
        break;
      }
      if (h(m, 2, 1, 3)) {
        ok = true;
        break;
      }
      if (h(m, 2, 3, 1)) {
        ok = true;
        break;
      }
      if (h(m, 3, 1, 2)) {
        ok = true;
        break;
      }
      if (h(m, 3, 2, 1)) {
        ok = true;
        break;
      }
      ref();
    }
    if (ok)
      l = m + 1;
    else
      r = m - 1;
  }
  printf("%d\n", r * 3);
  return 0;
}

```