Bajtazar is a logistics manager at a company that delivers supplies to stores. In the city where his company operates, the road network consists of horizontal streets (running from west to east) and vertical avenues (running from south to north). Each adjacent pair of streets and avenues is one kilometer apart. Streets are numbered with integers from south to north, and avenues are numbered from west to east. The intersection of the $i$-th avenue and the $j$-th street can be described as $(i, j)$. You may assume that for any integer, there exists both a street and an avenue with that number.

Bajtazar has planned $n$ deliveries for tomorrow; the $i$-th delivery will be carried out by a car that leaves its garage at time $t_i$ and travels along a street or avenue at a constant speed of one kilometer per unit of time. A delivery can be of one of two types: for a type one delivery, the garage is located at the intersection $(w_i, 0)$ and the car travels north along avenue $w_i$; for a type two delivery, the garage is located at the intersection $(0, w_i)$ and the car travels east along street $w_i$. According to the plan, at most one car leaves from each garage at any given moment.

Cars do not need to stop—while passing by the appropriate buildings, the drivers simply drop off the required package. However, there is a problem: if two delivery cars are at the same intersection at the same time, a collision will likely occur. Bajtazar would very much like to avoid this. Unfortunately, the only thing he can do is to cancel some deliveries entirely. He would therefore like to choose the minimum number of cars to cancel so that no two of the remaining cars are at the same intersection at the same time.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$), representing the number of planned deliveries.

The next $n$ lines contain descriptions of the planned deliveries; the $i$-th of these lines consists of three integers $r_i$, $w_i$, and $t_i$ ($r_i \in \{1, 2\}$; $1 \le w_i \le 10^6$; $0 \le t_i \le 10^6$), representing the type of the $i$-th delivery, the location of the garage, and the departure time.

Output

The output should contain a single integer representing the minimum possible number of deliveries that must be canceled.

Examples

Input 1

4
1 5 2
2 3 0
2 3 6
1 7 4

Output 1

1

Note

Attempting to carry out all four deliveries will cause a collision between the first and second cars at the intersection $(5, 3)$ at time $5$. After canceling the first delivery, we will still have a collision between the second and fourth cars at the intersection $(7, 3)$ at time $7$. On the other hand, after canceling the second delivery, none of the remaining cars will collide.