A Journey to Mars

Byteazar has decided to tour the space stations that exist around Mars. All the Martian space stations lie on the circumference of a single circle. Byteazar lands at one of them and then moves along the circle using a special vehicle powered by a suitable fuel. One litre of this fuel lets him travel exactly one metre.

Each station holds a different amount of fuel. Byteazar may refuel at the station he is currently in, but he cannot take more fuel than is available there (the capacity of his fuel tank is unlimited). The fuel he takes must be enough to reach the next station.

Byteazar has to decide where to land so that he can visit all of the stations. At the end he must return to the station where he landed. Throughout the journey Byteazar travels along the circumference, always continuing in one of the two possible directions.

Write a program which:

• reads from standard input the number of space stations, the distances between them, and the amount of fuel available at each of them,
• for each station determines whether Byteazar can land there — that is, whether by starting at that station and travelling in a freely chosen direction he can visit all the stations and return to his landing spot,
• writes the outcome to standard output.

The first line contains a single integer $N$ ($3 \le N \le 1{,}000{,}000$), the number of space stations on Mars. The stations are numbered from $1$ to $N$.

Each of the next $N$ lines describes one station and one distance. The $(i+1)$-th line contains two integers $p_i$ and $d_i$ ($p_i \ge 0$, $d_i > 0$). Here $p_i$ is the amount of fuel (in litres) available at the $i$-th station, and $d_i$ is the distance (in metres) between the $i$-th and $(i+1)$-th station (where $d_N$ is the distance between the $N$-th and the $1$st station).

The total amount of available fuel and the total of all distances between the stations each do not exceed $2{,}000{,}000{,}000$.

Print $N$ lines. The $i$-th line should contain TAK (Polish for “yes”) if Byteazar can land at the $i$-th station, or NIE (Polish for “no”) if it is not possible.