#include <bits/stdc++.h>
using namespace std;
int n, X[100005], Y[100005], C[100005];
int ax[100005], ay[100005], ix, iy;
struct Nod {
  int x, y, c;
  Nod(int _x = 0, int _y = 0, int _c = 0) : x(_x), y(_y), c(_c) {}
} dx[100005], dy[100005];
inline bool cmpx(const Nod &a, const Nod &b) { return a.x < b.x; }
inline bool cmpy(const Nod &a, const Nod &b) { return a.y < b.y; }
int getx(int i, int x, int v) {
  while (i && i <= n && dx[i].x == x) i += v;
  return i > n ? 0 : i;
}
int prex(int st, int c, int k) {
  if (!st) return 0;
  for (int i = st; i >= 1; --i)
    if (dx[i].c == c) {
      if (!(--k)) return i;
    }
  return 0;
}
int nxtx(int st, int c, int k) {
  if (!st) return 0;
  for (int i = st; i <= n; ++i)
    if (dx[i].c == c) {
      if (!(--k)) return i;
    }
  return 0;
}
int gety(int i, int y, int v) {
  while (i && i <= n && dy[i].y == y) i += v;
  return i > n ? 0 : i;
}
int prey(int st, int c, int k) {
  if (!st) return 0;
  for (int i = st; i >= 1; --i)
    if (dy[i].c == c) {
      if (!(--k)) return i;
    }
  return 0;
}
int nxty(int st, int c, int k) {
  if (!st) return 0;
  for (int i = st; i <= n; ++i)
    if (dy[i].c == c) {
      if (!(--k)) return i;
    }
  return 0;
}
bool Judge(int c1, int c2, int c3, int k) {
  int p, lft, lx, ly;
  p = 1;
  p = nxtx(p, c1, k);
  p = getx(p, dx[p].x, 1);
  p = nxtx(p, c2, k);
  p = getx(p, dx[p].x, 1);
  p = nxtx(p, c3, k);
  if (p) return true;
  p = 1;
  p = nxty(p, c1, k);
  p = gety(p, dy[p].y, 1);
  p = nxty(p, c2, k);
  p = gety(p, dy[p].y, 1);
  p = nxty(p, c3, k);
  if (p) return true;
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dx[i].c == c1) {
      if (!(--lft)) {
        lx = dx[i].x;
        break;
      }
    }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dy[i].c == c2 && dy[i].x > lx) {
      if (!(--lft)) {
        ly = dy[i].y;
        break;
      }
    }
  if (!lft) {
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dy[i].c == c3 && dy[i].x > lx && dy[i].y > ly) {
        if (!(--lft)) break;
      }
    if (!lft) return true;
  }
  lft = k;
  for (int i = n; i >= 1; --i)
    if (dx[i].c == c1) {
      if (!(--lft)) {
        lx = dx[i].x;
        break;
      }
    }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dy[i].c == c2 && dy[i].x < lx) {
      if (!(--lft)) {
        ly = dy[i].y;
        break;
      }
    }
  if (!lft) {
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dy[i].c == c3 && dy[i].x < lx && dy[i].y > ly) {
        if (!(--lft)) break;
      }
    if (!lft) return true;
  }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dy[i].c == c1) {
      if (!(--lft)) {
        ly = dy[i].y;
        break;
      }
    }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dx[i].c == c2 && dx[i].y > ly) {
      if (!(--lft)) {
        lx = dx[i].x;
        break;
      }
    }
  if (!lft) {
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dx[i].c == c3 && dx[i].x > lx && dx[i].y > ly) {
        if (!(--lft)) break;
      }
    if (!lft) return true;
  }
  lft = k;
  for (int i = n; i >= 1; --i)
    if (dy[i].c == c1) {
      if (!(--lft)) {
        ly = dy[i].y;
        break;
      }
    }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dx[i].c == c2 && dx[i].y < ly) {
      if (!(--lft)) {
        lx = dx[i].x;
        break;
      }
    }
  if (!lft) {
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dx[i].c == c3 && dx[i].x > lx && dx[i].y < ly) {
        if (!(--lft)) break;
      }
    if (!lft) return true;
  }
  return false;
}
bool check(int k) {
  int p[3] = {1, 2, 3};
  do {
    if (Judge(p[0], p[1], p[2], k)) return true;
  } while (next_permutation(p, p + 3));
  return false;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> X[i] >> Y[i] >> C[i];
    ax[++ix] = X[i];
    ay[++iy] = Y[i];
  }
  sort(ax + 1, ax + ix + 1);
  ix = unique(ax + 1, ax + ix + 1) - ax - 1;
  sort(ay + 1, ay + iy + 1);
  iy = unique(ay + 1, ay + iy + 1) - ay - 1;
  for (int i = 1; i <= n; ++i) {
    int x = lower_bound(ax + 1, ax + ix + 1, X[i]) - ax;
    int y = lower_bound(ay + 1, ay + iy + 1, Y[i]) - ay;
    dx[i] = Nod(x, y, C[i]);
    dy[i] = Nod(x, y, C[i]);
  }
  sort(dx + 1, dx + n + 1, cmpx);
  sort(dy + 1, dy + n + 1, cmpy);
  int l = 1, r = n / 3, mid;
  while (l < r) {
    mid = (l + r + 1) >> 1;
    if (check(mid))
      l = mid;
    else
      r = mid - 1;
  }
  cout << l * 3 << endl;
  return 0;
}

### 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>
using namespace std;
int n, X[100005], Y[100005], C[100005];
int ax[100005], ay[100005], ix, iy;
struct Nod {
  int x, y, c;
  Nod(int _x = 0, int _y = 0, int _c = 0) : x(_x), y(_y), c(_c) {}
} dx[100005], dy[100005];
inline bool cmpx(const Nod &a, const Nod &b) { return a.x < b.x; }
inline bool cmpy(const Nod &a, const Nod &b) { return a.y < b.y; }
int getx(int i, int x, int v) {
  while (i && i <= n && dx[i].x == x) i += v;
  return i > n ? 0 : i;
}
int prex(int st, int c, int k) {
  if (!st) return 0;
  for (int i = st; i >= 1; --i)
    if (dx[i].c == c) {
      if (!(--k)) return i;
    }
  return 0;
}
int nxtx(int st, int c, int k) {
  if (!st) return 0;
  for (int i = st; i <= n; ++i)
    if (dx[i].c == c) {
      if (!(--k)) return i;
    }
  return 0;
}
int gety(int i, int y, int v) {
  while (i && i <= n && dy[i].y == y) i += v;
  return i > n ? 0 : i;
}
int prey(int st, int c, int k) {
  if (!st) return 0;
  for (int i = st; i >= 1; --i)
    if (dy[i].c == c) {
      if (!(--k)) return i;
    }
  return 0;
}
int nxty(int st, int c, int k) {
  if (!st) return 0;
  for (int i = st; i <= n; ++i)
    if (dy[i].c == c) {
      if (!(--k)) return i;
    }
  return 0;
}
bool Judge(int c1, int c2, int c3, int k) {
  int p, lft, lx, ly;
  p = 1;
  p = nxtx(p, c1, k);
  p = getx(p, dx[p].x, 1);
  p = nxtx(p, c2, k);
  p = getx(p, dx[p].x, 1);
  p = nxtx(p, c3, k);
  if (p) return true;
  p = 1;
  p = nxty(p, c1, k);
  p = gety(p, dy[p].y, 1);
  p = nxty(p, c2, k);
  p = gety(p, dy[p].y, 1);
  p = nxty(p, c3, k);
  if (p) return true;
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dx[i].c == c1) {
      if (!(--lft)) {
        lx = dx[i].x;
        break;
      }
    }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dy[i].c == c2 && dy[i].x > lx) {
      if (!(--lft)) {
        ly = dy[i].y;
        break;
      }
    }
  if (!lft) {
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dy[i].c == c3 && dy[i].x > lx && dy[i].y > ly) {
        if (!(--lft)) break;
      }
    if (!lft) return true;
  }
  lft = k;
  for (int i = n; i >= 1; --i)
    if (dx[i].c == c1) {
      if (!(--lft)) {
        lx = dx[i].x;
        break;
      }
    }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dy[i].c == c2 && dy[i].x < lx) {
      if (!(--lft)) {
        ly = dy[i].y;
        break;
      }
    }
  if (!lft) {
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dy[i].c == c3 && dy[i].x < lx && dy[i].y > ly) {
        if (!(--lft)) break;
      }
    if (!lft) return true;
  }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dy[i].c == c1) {
      if (!(--lft)) {
        ly = dy[i].y;
        break;
      }
    }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dx[i].c == c2 && dx[i].y > ly) {
      if (!(--lft)) {
        lx = dx[i].x;
        break;
      }
    }
  if (!lft) {
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dx[i].c == c3 && dx[i].x > lx && dx[i].y > ly) {
        if (!(--lft)) break;
      }
    if (!lft) return true;
  }
  lft = k;
  for (int i = n; i >= 1; --i)
    if (dy[i].c == c1) {
      if (!(--lft)) {
        ly = dy[i].y;
        break;
      }
    }
  lft = k;
  for (int i = 1; i <= n; ++i)
    if (dx[i].c == c2 && dx[i].y < ly) {
      if (!(--lft)) {
        lx = dx[i].x;
        break;
      }
    }
  if (!lft) {
    lft = k;
    for (int i = 1; i <= n; ++i)
      if (dx[i].c == c3 && dx[i].x > lx && dx[i].y < ly) {
        if (!(--lft)) break;
      }
    if (!lft) return true;
  }
  return false;
}
bool check(int k) {
  int p[3] = {1, 2, 3};
  do {
    if (Judge(p[0], p[1], p[2], k)) return true;
  } while (next_permutation(p, p + 3));
  return false;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> X[i] >> Y[i] >> C[i];
    ax[++ix] = X[i];
    ay[++iy] = Y[i];
  }
  sort(ax + 1, ax + ix + 1);
  ix = unique(ax + 1, ax + ix + 1) - ax - 1;
  sort(ay + 1, ay + iy + 1);
  iy = unique(ay + 1, ay + iy + 1) - ay - 1;
  for (int i = 1; i <= n; ++i) {
    int x = lower_bound(ax + 1, ax + ix + 1, X[i]) - ax;
    int y = lower_bound(ay + 1, ay + iy + 1, Y[i]) - ay;
    dx[i] = Nod(x, y, C[i]);
    dy[i] = Nod(x, y, C[i]);
  }
  sort(dx + 1, dx + n + 1, cmpx);
  sort(dy + 1, dy + n + 1, cmpy);
  int l = 1, r = n / 3, mid;
  while (l < r) {
    mid = (l + r + 1) >> 1;
    if (check(mid))
      l = mid;
    else
      r = mid - 1;
  }
  cout << l * 3 << endl;
  return 0;
}

```