In the vast African desert lives a tribe of hardworking and brave alpacas. The leader of this tribe, known to his people as the "Prophet" Alpaca L. Sotomon, is also called "King Sotomon" by outsiders. King Sotomon dedicated his life to maintaining the stability and harmony of his tribe; he personally led his army to crush the barbaric aggression of the River Crab Empire, earning great merits for his people. King Sotomon possessed countless treasures throughout his life, but due to his frugal and low-key nature, he buried his treasures in an underground palace he designed himself. This is where the story of Henry Curtis begins.

Henry is a greedy fellow who loves money above all else, but he is also very clever. He meticulously planned this theft and, after breaking through numerous mechanisms, arrived in front of this underground palace.

The entire palace is in the form of a matrix, consisting of $R \times C$ rectangular chambers. Among them, $N$ chambers contain treasures, which are called treasure chambers. The outside of the palace and adjacent chambers are separated by solid walls. One can only travel from one chamber to another using the unique movement method created by King Sotomon—teleportation portals. King Sotomon installed a portal in each of these $N$ treasure chambers; chambers without treasure do not have portals. All portals are divided into three types:

1. "Horizontal Gate": From this gate, one can teleport to any chamber in the same row.
2. "Vertical Gate": From this gate, one can teleport to any chamber in the same column.
3. "Free Gate": From this gate, one can teleport to any of the 8 surrounding chambers (if the target chamber exists).

The deep-thinking Henry had, of course, obtained the palace's original tender documents in advance, which recorded in detail the location and type of every portal. Furthermore, although the palace is sealed off from the outside, he prepared a portable portal that allows him to teleport into any chamber in the palace to start his treasure hunt and teleport out from any chamber when finished. The entire palace can only be entered and exited once, and the portable portal cannot be used for travel between chambers inside the palace. Fortunately, there is no limit to the number of times the internal portals can be used, and each chamber can be entered and exited multiple times.

Now that Henry has opened his portable portal and is about to choose a chamber to enter, he wants to arrange a route to visit as many different treasure chambers as possible to obtain the most treasure. Please tell Henry the maximum number of different treasure chambers he can visit.

Input

The first line contains three positive integers $N, R, C$.

The following $N$ lines each provide information about a portal, containing three positive integers $x_i, y_i, T_i$, representing that the portal is located in the treasure chamber at row $x_i$ and column $y_i$, with type $T_i$. $T_i$ is an integer from $1$ to $3$, where $1$ represents a "Horizontal Gate" that can teleport to any column in row $x_i$, $2$ represents a "Vertical Gate" that can teleport to any row in column $y_i$, and $3$ represents a "Free Gate" that can teleport to the 8 surrounding chambers.

It is guaranteed that $1 \le x_i \le R$, $1 \le y_i \le C$, and all portal locations are distinct.

Output

A single positive integer representing the maximum number of different treasure chambers that can be visited on your determined route.

Examples

Input 1

10 7 7
2 2 1
2 4 2
1 7 2
2 7 3
4 2 2
4 4 1
6 7 3
7 7 1
7 5 2
5 2 1

Output 1

9

Constraints