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

Input

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.

Output

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

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