P3422 [POI 2005] LOT-A Journey to Mars

Byteazar decided to travel to Mars to join a space station tour.

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.

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 $n$ lines, each containing the string `TAK` or `NIE`. If landing at station $i$ is feasible, print `TAK` on line $i$; otherwise, print `NIE`.

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