There are $n$ gas stations numbered from $1$ to $n$ on a ring road (you can travel between gas station $i$ and $i+1$, as well as between gas station $1$ and $n$). You need to start at any gas station, travel through all the gas stations either clockwise or counterclockwise, and return to the starting point. Initially, your vehicle has no fuel. At gas station $i$, you can refuel $p_i$ liters of gasoline, and each liter allows you to travel 1 kilometer. For each gas station, determine if it is possible to start at that station and complete the journey.

Input

• The first line contains an integer $n$.
• The second line contains two integers $p_i$ and $r_i$, representing the amount of gasoline at station $i$ and the distance to the next gas station, regardless of direction.

Output

• Print $n$ lines, where the $i$-th line contains TAK if it is possible to start at station $i$ and complete the journey, otherwise print NIE.

Constraints

• $1 \le n \le 10^6$.
• $0 \le p_i, d_i \le 2 \times 10^9$.

Example

Input:

5
3 1
1 2
5 2
0 1
5 4

Output:

TAK
NIE
TAK
NIE
TAK