Description

All space stations on Mars lie on a circle. Byteazar lands at one of the stations and then starts traveling around the circle.

Travel consumes fuel: $1$ liter of fuel allows traveling $1$ meter. Each station provides a different amount of fuel.

At each station, Byteazar may take all the fuel available there (his fuel tank has no capacity limit). However, if at any moment he runs out of fuel while moving, the trip fails.

Byteazar needs to decide at which station to land so that he can successfully visit all stations and return to his starting station. After landing, he may choose either direction to travel.

Input Format

The first line contains an integer $n$, the number of stations. The stations are numbered from $1$ to $n$.

Then follow $n$ lines. Each of the next $n$ lines contains two integers $p_i, d_i$. The $(i + 1)$-th line describes station $i$, where $p_i$ is the amount of fuel available at station $i$, and $d_i$ is the distance from station $i$ to station $i + 1$. For station $n$, $d_i$ is the distance from station $n$ to station $1$.

Output Format

Output $n$ lines, each containing the string TAK or NIE.

If landing at station $i$ is feasible, print TAK on line $i$; otherwise, print NIE.

5
3 1
1 2
5 2
0 1
5 4

TAK
NIE
TAK
NIE
TAK

Hint

Constraints

For $100\%$ of the testdata, $3 \le n \le 10^6$, $p_i \ge 0$, $d_i > 0$, and $\sum d_i, \sum p_i \le 2 \times 10^9$.

Translated by ChatGPT 5