#include <bits/stdc++.h>
using namespace std;
struct colorcount_t {
  int many[3];
  colorcount_t() {
    for (int i = 0; i < 3; ++i) many[i] = 0;
  }
};
struct separator_t {
  struct query_t {
    int low, high;
    int many_low, many_high;
    map<int, colorcount_t>::iterator it;
    void update(map<int, colorcount_t> &counts) {
      while (many_low > many_high && it != counts.begin()) {
        --it;
        many_low -= it->second.many[low];
        many_high += it->second.many[high];
      }
      while (many_low < many_high && it != counts.end()) {
        many_high -= it->second.many[high];
        many_low += it->second.many[low];
        ++it;
      }
      if (it != counts.begin()) {
        auto it2 = it;
        --it2;
        int many_low2 = many_low - it2->second.many[low];
        int many_high2 = many_high + it2->second.many[high];
        if (min(many_low2, many_high2) > result()) {
          it = it2;
          many_low = many_low2;
          many_high = many_high2;
        }
      }
    }
    int result() const { return min(many_low, many_high); }
  };
  vector<query_t> queries;
  map<int, colorcount_t> counts;
  separator_t() {
    for (int i = 0; i < 3; ++i)
      for (int j = 0; j < 3; ++j)
        if (i != j) queries.push_back({i, j, 0, 0, counts.end()});
  }
  void add(int pos, int added_color) {
    counts[pos].many[added_color] += 1;
    for (query_t &q : queries) {
      if (q.it == counts.end() || pos < q.it->first) {
        if (q.low == added_color) q.many_low += 1;
      } else {
        if (q.high == added_color) q.many_high += 1;
      }
      q.update(counts);
    }
  }
};
int main() {
  int n;
  scanf("%d", &n);
  struct point_t {
    int x, y, c;
  };
  vector<point_t> points(n);
  for (int i = 0; i < n; ++i)
    scanf("%d %d %d", &points[i].x, &points[i].y, &points[i].c), --points[i].c;
  int result = 0;
  for (int rep = 0; rep < 2; ++rep) {
    colorcount_t cc;
    for (int i = 0; i < n; ++i) cc.many[points[i].c] += 1;
    sort(points.begin(), points.end(),
         [](const point_t &lhs, const point_t &rhs) { return lhs.x < rhs.x; });
    separator_t sep;
    for (int i = 0, j = i; i != n; i = j) {
      while (j != n && points[j].x == points[i].x) ++j;
      for (int k = i; k < j; ++k) {
        sep.add(points[k].x, points[k].c);
        cc.many[points[k].c] -= 1;
      }
      for (const separator_t::query_t &q : sep.queries) {
        int other = 0 ^ 1 ^ 2 ^ q.low ^ q.high;
        int res = min(q.result(), cc.many[other]);
        result = max(result, res);
      }
    }
    for (int i = 0; i < n; ++i) swap(points[i].x, points[i].y);
  }
  for (int rep1 = 0; rep1 < 2; ++rep1) {
    for (int rep2 = 0; rep2 < 2; ++rep2) {
      colorcount_t cc;
      for (int i = 0; i < n; ++i) cc.many[points[i].c] += 1;
      sort(
          points.begin(), points.end(),
          [](const point_t &lhs, const point_t &rhs) { return lhs.x < rhs.x; });
      separator_t sep;
      for (int i = 0, j = i; i != n; i = j) {
        while (j != n && points[j].x == points[i].x) ++j;
        for (int k = i; k < j; ++k) {
          sep.add(points[k].y, points[k].c);
          cc.many[points[k].c] -= 1;
        }
        for (const separator_t::query_t &q : sep.queries) {
          int other = 0 ^ 1 ^ 2 ^ q.low ^ q.high;
          int res = min(q.result(), cc.many[other]);
          result = max(result, res);
        }
      }
      for (int i = 0; i < n; ++i) points[i].x = -points[i].x;
    }
    for (int i = 0; i < n; ++i) swap(points[i].x, points[i].y);
  }
  printf("%d\n", result * 3);
  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;
struct colorcount_t {
  int many[3];
  colorcount_t() {
    for (int i = 0; i < 3; ++i) many[i] = 0;
  }
};
struct separator_t {
  struct query_t {
    int low, high;
    int many_low, many_high;
    map<int, colorcount_t>::iterator it;
    void update(map<int, colorcount_t> &counts) {
      while (many_low > many_high && it != counts.begin()) {
        --it;
        many_low -= it->second.many[low];
        many_high += it->second.many[high];
      }
      while (many_low < many_high && it != counts.end()) {
        many_high -= it->second.many[high];
        many_low += it->second.many[low];
        ++it;
      }
      if (it != counts.begin()) {
        auto it2 = it;
        --it2;
        int many_low2 = many_low - it2->second.many[low];
        int many_high2 = many_high + it2->second.many[high];
        if (min(many_low2, many_high2) > result()) {
          it = it2;
          many_low = many_low2;
          many_high = many_high2;
        }
      }
    }
    int result() const { return min(many_low, many_high); }
  };
  vector<query_t> queries;
  map<int, colorcount_t> counts;
  separator_t() {
    for (int i = 0; i < 3; ++i)
      for (int j = 0; j < 3; ++j)
        if (i != j) queries.push_back({i, j, 0, 0, counts.end()});
  }
  void add(int pos, int added_color) {
    counts[pos].many[added_color] += 1;
    for (query_t &q : queries) {
      if (q.it == counts.end() || pos < q.it->first) {
        if (q.low == added_color) q.many_low += 1;
      } else {
        if (q.high == added_color) q.many_high += 1;
      }
      q.update(counts);
    }
  }
};
int main() {
  int n;
  scanf("%d", &n);
  struct point_t {
    int x, y, c;
  };
  vector<point_t> points(n);
  for (int i = 0; i < n; ++i)
    scanf("%d %d %d", &points[i].x, &points[i].y, &points[i].c), --points[i].c;
  int result = 0;
  for (int rep = 0; rep < 2; ++rep) {
    colorcount_t cc;
    for (int i = 0; i < n; ++i) cc.many[points[i].c] += 1;
    sort(points.begin(), points.end(),
         [](const point_t &lhs, const point_t &rhs) { return lhs.x < rhs.x; });
    separator_t sep;
    for (int i = 0, j = i; i != n; i = j) {
      while (j != n && points[j].x == points[i].x) ++j;
      for (int k = i; k < j; ++k) {
        sep.add(points[k].x, points[k].c);
        cc.many[points[k].c] -= 1;
      }
      for (const separator_t::query_t &q : sep.queries) {
        int other = 0 ^ 1 ^ 2 ^ q.low ^ q.high;
        int res = min(q.result(), cc.many[other]);
        result = max(result, res);
      }
    }
    for (int i = 0; i < n; ++i) swap(points[i].x, points[i].y);
  }
  for (int rep1 = 0; rep1 < 2; ++rep1) {
    for (int rep2 = 0; rep2 < 2; ++rep2) {
      colorcount_t cc;
      for (int i = 0; i < n; ++i) cc.many[points[i].c] += 1;
      sort(
          points.begin(), points.end(),
          [](const point_t &lhs, const point_t &rhs) { return lhs.x < rhs.x; });
      separator_t sep;
      for (int i = 0, j = i; i != n; i = j) {
        while (j != n && points[j].x == points[i].x) ++j;
        for (int k = i; k < j; ++k) {
          sep.add(points[k].y, points[k].c);
          cc.many[points[k].c] -= 1;
        }
        for (const separator_t::query_t &q : sep.queries) {
          int other = 0 ^ 1 ^ 2 ^ q.low ^ q.high;
          int res = min(q.result(), cc.many[other]);
          result = max(result, res);
        }
      }
      for (int i = 0; i < n; ++i) points[i].x = -points[i].x;
    }
    for (int i = 0; i < n; ++i) swap(points[i].x, points[i].y);
  }
  printf("%d\n", result * 3);
  return 0;
}

```