#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:512000000")
using namespace std;
using li = long long;
using ld = long double;
void solve(bool);
void precalc();
clock_t start;
int main() {
  start = clock();
  int t = 1;
  cout.sync_with_stdio(0);
  cin.tie(0);
  cout.precision(20);
  cout << fixed;
  precalc();
  int test_num = 1;
  while (t--) {
    solve(true);
  }
  cout.flush();
  return 0;
}
template <typename T>
T binpow(T q, T w, T mod) {
  if (!w) return 1 % mod;
  if (w & 1) return q * 1LL * binpow(q, w - 1, mod) % mod;
  return binpow(q * 1LL * q % mod, w / 2, mod);
}
template <typename T>
T gcd(T q, T w) {
  while (w) {
    q %= w;
    swap(q, w);
  }
  return q;
}
template <typename T>
T lcm(T q, T w) {
  return q / gcd(q, w) * w;
}
template <typename T>
void make_unique(vector<T>& vec) {
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
template <typename T>
void relax_min(T& cur, T val) {
  cur = min(cur, val);
}
template <typename T>
void relax_max(T& cur, T val) {
  cur = max(cur, val);
}
mt19937 rng(
    (unsigned long long)chrono::steady_clock::now().time_since_epoch().count());
void precalc() {}
struct Point {
  int x, y;
  Point(int x = 0, int y = 0) : x(x), y(y) {}
  Point rotate() const { return Point(y, -x); }
  Point reflect() const { return Point(-x, y); }
  void scan() { cin >> x >> y; }
  bool operator<(const Point& ot) const {
    return make_pair(x, y) < make_pair(ot.x, ot.y);
  }
};
void solve(__attribute__((unused)) bool read) {
  int n;
  cin >> n;
  vector<vector<Point>> points(3);
  for (int i = 0; i < n; ++i) {
    Point cur;
    cur.scan();
    int type;
    cin >> type;
    points[type - 1].push_back(cur);
  }
  const int INF = (int)1e9 + 100;
  int ans = 0;
  for (int reflect = 0; reflect < 2; ++reflect) {
    for (int rotate = 0; rotate < 4; ++rotate) {
      auto points_by_y = points;
      for (int i = 0; i < 3; ++i) {
        sort(points[i].begin(), points[i].end());
        sort(points_by_y[i].begin(), points_by_y[i].end(),
             [&](const Point& q, const Point& w) { return q.y < w.y; });
      }
      vector<int> perm(3);
      iota(perm.begin(), perm.end(), 0);
      do {
        int last = perm[2], first = perm[0], mid = perm[1];
        auto border_by_x = [&](int cnt, int border) {
          int pos = -1;
          for (int i = n / 3 - 1; i >= 0; --i) {
            if (points[mid][i].x < border) {
              pos = i - cnt + 1;
              break;
            }
          }
          if (pos < 0) {
            return false;
          }
          border = points[mid][pos].x;
          return points[first][cnt - 1].x < border;
        };
        auto is_good = [&](int cnt) {
          int border = points[last][n / 3 - cnt].x;
          if (border_by_x(cnt, border)) {
            return true;
          }
          int cnt_found = 0;
          int first_y = -INF;
          for (auto pt : points_by_y[first]) {
            if (pt.x >= border) {
              continue;
            }
            ++cnt_found;
            first_y = pt.y;
            if (cnt_found == cnt) {
              break;
            }
          }
          if (cnt_found < cnt) {
            return false;
          }
          cnt_found = 0;
          int mid_y = INF;
          for (int i = n / 3 - 1; i >= 0; --i) {
            auto pt = points_by_y[mid][i];
            if (pt.x >= border) {
              continue;
            }
            ++cnt_found;
            mid_y = pt.y;
            if (cnt_found == cnt) {
              break;
            }
          }
          if (cnt_found < cnt) {
            return false;
          }
          return first_y < mid_y;
        };
        int L = 0, R = n / 3 + 1;
        while (L + 1 < R) {
          int M = (L + R) / 2;
          if (is_good(M)) {
            L = M;
          } else {
            R = M;
          }
        }
        relax_max(ans, L);
      } while (next_permutation(perm.begin(), perm.end()));
      for (auto& vec : points) {
        for (auto& pt : vec) {
          pt = pt.rotate();
        }
      }
    }
    for (auto& vec : points) {
      for (auto& pt : vec) {
        pt = pt.reflect();
      }
    }
  }
  cout << ans * 3 << "\n";
}

### Prompt

Create a solution in Cpp for 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>
#pragma comment(linker, "/STACK:512000000")
using namespace std;
using li = long long;
using ld = long double;
void solve(bool);
void precalc();
clock_t start;
int main() {
  start = clock();
  int t = 1;
  cout.sync_with_stdio(0);
  cin.tie(0);
  cout.precision(20);
  cout << fixed;
  precalc();
  int test_num = 1;
  while (t--) {
    solve(true);
  }
  cout.flush();
  return 0;
}
template <typename T>
T binpow(T q, T w, T mod) {
  if (!w) return 1 % mod;
  if (w & 1) return q * 1LL * binpow(q, w - 1, mod) % mod;
  return binpow(q * 1LL * q % mod, w / 2, mod);
}
template <typename T>
T gcd(T q, T w) {
  while (w) {
    q %= w;
    swap(q, w);
  }
  return q;
}
template <typename T>
T lcm(T q, T w) {
  return q / gcd(q, w) * w;
}
template <typename T>
void make_unique(vector<T>& vec) {
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
template <typename T>
void relax_min(T& cur, T val) {
  cur = min(cur, val);
}
template <typename T>
void relax_max(T& cur, T val) {
  cur = max(cur, val);
}
mt19937 rng(
    (unsigned long long)chrono::steady_clock::now().time_since_epoch().count());
void precalc() {}
struct Point {
  int x, y;
  Point(int x = 0, int y = 0) : x(x), y(y) {}
  Point rotate() const { return Point(y, -x); }
  Point reflect() const { return Point(-x, y); }
  void scan() { cin >> x >> y; }
  bool operator<(const Point& ot) const {
    return make_pair(x, y) < make_pair(ot.x, ot.y);
  }
};
void solve(__attribute__((unused)) bool read) {
  int n;
  cin >> n;
  vector<vector<Point>> points(3);
  for (int i = 0; i < n; ++i) {
    Point cur;
    cur.scan();
    int type;
    cin >> type;
    points[type - 1].push_back(cur);
  }
  const int INF = (int)1e9 + 100;
  int ans = 0;
  for (int reflect = 0; reflect < 2; ++reflect) {
    for (int rotate = 0; rotate < 4; ++rotate) {
      auto points_by_y = points;
      for (int i = 0; i < 3; ++i) {
        sort(points[i].begin(), points[i].end());
        sort(points_by_y[i].begin(), points_by_y[i].end(),
             [&](const Point& q, const Point& w) { return q.y < w.y; });
      }
      vector<int> perm(3);
      iota(perm.begin(), perm.end(), 0);
      do {
        int last = perm[2], first = perm[0], mid = perm[1];
        auto border_by_x = [&](int cnt, int border) {
          int pos = -1;
          for (int i = n / 3 - 1; i >= 0; --i) {
            if (points[mid][i].x < border) {
              pos = i - cnt + 1;
              break;
            }
          }
          if (pos < 0) {
            return false;
          }
          border = points[mid][pos].x;
          return points[first][cnt - 1].x < border;
        };
        auto is_good = [&](int cnt) {
          int border = points[last][n / 3 - cnt].x;
          if (border_by_x(cnt, border)) {
            return true;
          }
          int cnt_found = 0;
          int first_y = -INF;
          for (auto pt : points_by_y[first]) {
            if (pt.x >= border) {
              continue;
            }
            ++cnt_found;
            first_y = pt.y;
            if (cnt_found == cnt) {
              break;
            }
          }
          if (cnt_found < cnt) {
            return false;
          }
          cnt_found = 0;
          int mid_y = INF;
          for (int i = n / 3 - 1; i >= 0; --i) {
            auto pt = points_by_y[mid][i];
            if (pt.x >= border) {
              continue;
            }
            ++cnt_found;
            mid_y = pt.y;
            if (cnt_found == cnt) {
              break;
            }
          }
          if (cnt_found < cnt) {
            return false;
          }
          return first_y < mid_y;
        };
        int L = 0, R = n / 3 + 1;
        while (L + 1 < R) {
          int M = (L + R) / 2;
          if (is_good(M)) {
            L = M;
          } else {
            R = M;
          }
        }
        relax_max(ans, L);
      } while (next_permutation(perm.begin(), perm.end()));
      for (auto& vec : points) {
        for (auto& pt : vec) {
          pt = pt.rotate();
        }
      }
    }
    for (auto& vec : points) {
      for (auto& pt : vec) {
        pt = pt.reflect();
      }
    }
  }
  cout << ans * 3 << "\n";
}

```