CF1608E.The Cells on the Paper

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 $\frac{n}{3}$ marked cells of each of three colors!

Find the largest such $k$ that it's possible to choose $\frac{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$.

在一张无限大的方格纸上，选取 $n$ 个格子并用三种颜色染色，其中 $n$ 是 $3$ 的倍数。结果发现，每种颜色恰好有 $\frac{n}{3}$ 个被染色的格子！

求最大的 $k$，使得可以从中选出每种颜色各 $\frac{k}{3}$ 个格子，移除其余所有被染色的格子，然后选取三个边与网格线平行的矩形，满足以下条件：

• 任意两个矩形不能相交（但可共享边界的一部分）。即：任意两个矩形的交集面积必须为 $0$。
• 第 $i$ 个矩形（$i = 1, 2, 3$）恰好包含所选出的第 $i$ 种颜色的所有格子，且不包含所选出的其他颜色的任何格子。

The first line of the input contains a single integer $n$ — the number of the marked cells ($3 \leq n \le 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| \leq 10^9$; $1 \leq c_i \leq 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 $\frac{n}{3}$ cells of each color.

输入的第一行包含一个整数 $n$ —— 标记格子的数量（$3 \leq n \le 10^5$，且 $n$ 能被 $3$ 整除）。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $x_i$、$y_i$、$c_i$（$|x_i|,|y_i| \leq 10^9$；$1 \leq c_i \leq 3$），其中 $(x_i, y_i)$ 是第 $i$ 个标记格子的坐标，$c_i$ 是其颜色。

保证输入中所有格子 $(x_i, y_i)$ 互不相同，且每种颜色的格子数量恰好为 $\frac{n}{3}$。

Output a single integer $k$ — the largest number of cells you can leave.

输出一个整数 $k$ —— 你能保留的最多格子数。

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$.

在第一个样例中，可以保留索引为 $1, 5, 6, 7, 8, 9$ 的 $6$ 个格子。

在第二个样例中，可以保留索引为 $1, 2, 3$ 的 $3$ 个格子。