#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using datas = pair<ll, ll>;
using ddatas = pair<long double, long double>;
using tdata = pair<ll, datas>;
using vec = vector<ll>;
using mat = vector<vec>;
using pvec = vector<datas>;
using pmat = vector<pvec>;
constexpr ll mod = 998244353;
constexpr ll inf = 1LL << 60;
constexpr long double eps = 1e-9;
const long double PI = acosl(-1);
template <class T, class E>
ostream& operator<<(ostream& os, const pair<T, E>& p) {
  return os << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  bool f = false;
  for (auto& x : v) {
    if (f) os << ",";
    os << x;
    f = true;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
  os << "{";
  bool f = false;
  for (auto& x : v) {
    if (f) os << ",";
    os << x;
    f = true;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  os << "{";
  bool f = false;
  for (auto& x : v) {
    if (f) os << ",";
    os << x;
    f = true;
  }
  os << "}";
  return os;
}
template <class T, class E>
ostream& operator<<(ostream& os, const map<T, E>& v) {
  os << "{";
  bool f = false;
  for (auto& x : v) {
    if (f) os << ",";
    os << x;
    f = true;
  }
  os << "}";
  return os;
}
template <class T>
inline bool chmax(T& a, const T b) {
  bool x = a < b;
  if (x) a = b;
  return x;
}
template <class T>
inline bool chmin(T& a, const T b) {
  bool x = a > b;
  if (x) a = b;
  return x;
}
inline void startupcpp(void) noexcept {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
ll N;
ll solve1(pvec a, pvec b, pvec c) {
  ll ok = 0, ng = N + 1;
  sort((a).begin(), (a).end());
  sort((b).begin(), (b).end(),
       [](datas l, datas r) { return l.second < r.second; });
  while (ng - ok > 1) {
    ll mid = (ok + ng) / 2;
    ll axmax = a[mid - 1].first;
    ll i, cnt = 0;
    for (i = 0; i < (ll)N; ++i) {
      if (b[i].first <= axmax) continue;
      ++cnt;
      if (cnt == mid) break;
    }
    if (i == N) {
      ng = mid;
      continue;
    }
    ll bymax = b[i].second;
    cnt = 0;
    for (i = 0; i < (ll)N; ++i) {
      if (c[i].first <= axmax || c[i].second <= bymax) continue;
      ++cnt;
      if (cnt == mid) break;
    }
    if (i == N) {
      ng = mid;
      continue;
    }
    ok = mid;
  }
  return ok;
}
ll solve2(pvec a, pvec b, pvec c) {
  sort((a).begin(), (a).end());
  sort((b).begin(), (b).end());
  sort((c).begin(), (c).end());
  ll ok = 0, ng = N + 1;
  while (ng - ok > 1) {
    ll mid = (ok + ng) / 2;
    ll axmax = a[mid - 1].first;
    ll i, cnt = 0;
    for (i = 0; i < (ll)N; ++i) {
      if (b[i].first <= axmax) continue;
      ++cnt;
      if (cnt == mid) break;
    }
    if (i == N) {
      ng = mid;
      continue;
    }
    ll bxmax = b[i].first;
    cnt = 0;
    for (i = 0; i < (ll)N; ++i) {
      if (c[i].first <= bxmax) continue;
      ++cnt;
      if (cnt == mid) break;
    }
    if (i == N) {
      ng = mid;
      continue;
    }
    ok = mid;
  }
  return ok;
}
int main() {
  startupcpp();
  cin >> N;
  pvec v[3];
  ll i, x, y;
  for (i = 0; i < (ll)N; ++i) {
    ll c;
    cin >> x >> y >> c;
    v[c - 1].emplace_back(x, y);
  }
  N /= 3;
  ll ch, ans = 0;
  for (ch = 0; ch < (ll)2; ++ch) {
    for (x = 0; x < (ll)2; ++x) {
      for (y = 0; y < (ll)2; ++y) {
        vec p = {0, 1, 2};
        do {
          chmax(ans, solve1(v[p[0]], v[p[1]], v[p[2]]));
          chmax(ans, solve2(v[p[0]], v[p[1]], v[p[2]]));
        } while (next_permutation((p).begin(), (p).end()));
        for (i = 0; i < (ll)3; ++i)
          for (auto& x : v[i]) x.second = -x.second;
      }
      for (i = 0; i < (ll)3; ++i)
        for (auto& x : v[i]) x.first = -x.first;
    }
    for (i = 0; i < (ll)3; ++i)
      for (auto& x : v[i]) swap(x.first, x.second);
  }
  cout << ans * 3 << "\n";
}

### Prompt

Generate 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>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using datas = pair<ll, ll>;
using ddatas = pair<long double, long double>;
using tdata = pair<ll, datas>;
using vec = vector<ll>;
using mat = vector<vec>;
using pvec = vector<datas>;
using pmat = vector<pvec>;
constexpr ll mod = 998244353;
constexpr ll inf = 1LL << 60;
constexpr long double eps = 1e-9;
const long double PI = acosl(-1);
template <class T, class E>
ostream& operator<<(ostream& os, const pair<T, E>& p) {
  return os << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  bool f = false;
  for (auto& x : v) {
    if (f) os << ",";
    os << x;
    f = true;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
  os << "{";
  bool f = false;
  for (auto& x : v) {
    if (f) os << ",";
    os << x;
    f = true;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  os << "{";
  bool f = false;
  for (auto& x : v) {
    if (f) os << ",";
    os << x;
    f = true;
  }
  os << "}";
  return os;
}
template <class T, class E>
ostream& operator<<(ostream& os, const map<T, E>& v) {
  os << "{";
  bool f = false;
  for (auto& x : v) {
    if (f) os << ",";
    os << x;
    f = true;
  }
  os << "}";
  return os;
}
template <class T>
inline bool chmax(T& a, const T b) {
  bool x = a < b;
  if (x) a = b;
  return x;
}
template <class T>
inline bool chmin(T& a, const T b) {
  bool x = a > b;
  if (x) a = b;
  return x;
}
inline void startupcpp(void) noexcept {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
ll N;
ll solve1(pvec a, pvec b, pvec c) {
  ll ok = 0, ng = N + 1;
  sort((a).begin(), (a).end());
  sort((b).begin(), (b).end(),
       [](datas l, datas r) { return l.second < r.second; });
  while (ng - ok > 1) {
    ll mid = (ok + ng) / 2;
    ll axmax = a[mid - 1].first;
    ll i, cnt = 0;
    for (i = 0; i < (ll)N; ++i) {
      if (b[i].first <= axmax) continue;
      ++cnt;
      if (cnt == mid) break;
    }
    if (i == N) {
      ng = mid;
      continue;
    }
    ll bymax = b[i].second;
    cnt = 0;
    for (i = 0; i < (ll)N; ++i) {
      if (c[i].first <= axmax || c[i].second <= bymax) continue;
      ++cnt;
      if (cnt == mid) break;
    }
    if (i == N) {
      ng = mid;
      continue;
    }
    ok = mid;
  }
  return ok;
}
ll solve2(pvec a, pvec b, pvec c) {
  sort((a).begin(), (a).end());
  sort((b).begin(), (b).end());
  sort((c).begin(), (c).end());
  ll ok = 0, ng = N + 1;
  while (ng - ok > 1) {
    ll mid = (ok + ng) / 2;
    ll axmax = a[mid - 1].first;
    ll i, cnt = 0;
    for (i = 0; i < (ll)N; ++i) {
      if (b[i].first <= axmax) continue;
      ++cnt;
      if (cnt == mid) break;
    }
    if (i == N) {
      ng = mid;
      continue;
    }
    ll bxmax = b[i].first;
    cnt = 0;
    for (i = 0; i < (ll)N; ++i) {
      if (c[i].first <= bxmax) continue;
      ++cnt;
      if (cnt == mid) break;
    }
    if (i == N) {
      ng = mid;
      continue;
    }
    ok = mid;
  }
  return ok;
}
int main() {
  startupcpp();
  cin >> N;
  pvec v[3];
  ll i, x, y;
  for (i = 0; i < (ll)N; ++i) {
    ll c;
    cin >> x >> y >> c;
    v[c - 1].emplace_back(x, y);
  }
  N /= 3;
  ll ch, ans = 0;
  for (ch = 0; ch < (ll)2; ++ch) {
    for (x = 0; x < (ll)2; ++x) {
      for (y = 0; y < (ll)2; ++y) {
        vec p = {0, 1, 2};
        do {
          chmax(ans, solve1(v[p[0]], v[p[1]], v[p[2]]));
          chmax(ans, solve2(v[p[0]], v[p[1]], v[p[2]]));
        } while (next_permutation((p).begin(), (p).end()));
        for (i = 0; i < (ll)3; ++i)
          for (auto& x : v[i]) x.second = -x.second;
      }
      for (i = 0; i < (ll)3; ++i)
        for (auto& x : v[i]) x.first = -x.first;
    }
    for (i = 0; i < (ll)3; ++i)
      for (auto& x : v[i]) swap(x.first, x.second);
  }
  cout << ans * 3 << "\n";
}

```