L3422 [POI 2005] LOT-A Journey to Mars

题目背景

Byteazar 决定去火星参加一个空间站旅行。

火星的所有空间站都位于一个圆上，Byteazar 在其中一个空间站登陆然后开始绕圈旅行。

旅行需要耗费油料，一升油料只能跑 $1$ 米，每个空间站可以补给的油料都有所不同。

Byteazar 每到一个空间站便可以把该空间站的油料全部拿走（他的油箱是没有容量限制的）。但是如果走到某个时候突然没油了那么旅行便失败了。

Byteazar 需要决定要在哪个地方登陆使得他能顺利访问完所有的空间站后回到他当初登陆的地方，他登陆后可以选择两个方向中的任意一个进行旅行。

第一行一个整数 $n$ ，代表空间站数量，所有空间站由 $1$ 至 $n$ 进行标号。

之后 $n$ 行，每行两个整数 $p_i,d_i$ ，第 $i + 1$ 行描述了第 $i$ 号空间站的信息，其中 $p_i$ 表示该空间站可以补给的油量， $d_i$ 则指明了它到 $i+1$ 号空间站的距离，对于 $n$ 号空间站， $d_i$ 表示它和 $1$ 号空间站的距离。

输出 $n$ 行，每行一个字符串 TAK 或 NIE。

若你认为在 $i$ 号空间站登陆是可行的，则需要在第 $i$ 行输出 TAK，否则输出 NIE。

TAK
NIE
TAK
NIE
TAK

对于 $100\%$ 的数据， $3\le n\le10^6$ ， $p_i\ge0$ ， $d_i>0$ ， $\sum d_i\le2\times10^9$ 。