[POI2005]Lot-A Journey to Mars

Byteazar 决定前往火星进行一次空间站之旅。火星上的所有空间站都位于同一个圆周上。Byteazar 将在其中一个空间站登陆，并从该空间站出发，沿圆周访问所有空间站，最后回到出发点。

旅行需要消耗燃料，每行驶 $1$ 米需要消耗 $1$ 升燃料。每个空间站都储存有一定量的燃料，Byteazar 到达一个空间站后，可以取走该空间站储存的全部燃料。他的油箱容量没有限制，但如果途中燃料耗尽且无法继续前进，则旅行失败。

Byteazar 需要判断：分别以每个空间站作为登陆点时，是否能够访问所有空间站并返回该登陆点。登陆后，他可以任选圆周上的一个方向行进，但在旅行途中不能改变方向。

输入格式

第一行包含一个整数 $N$，表示空间站的数量。空间站依次编号为 $1$ 到 $N$。

接下来 $N$ 行，第 $i$ 行包含两个整数 $p_i$ 和 $d_i$，其中：

• $p_i$ 表示第 $i$ 个空间站储存的燃料量；
• $d_i$ 表示第 $i$ 个空间站与第 $i+1$ 个空间站之间的距离。

其中，$d_N$ 表示第 $N$ 个空间站与第 $1$ 个空间站之间的距离。

输出格式

输出 $N$ 行。

第 $i$ 行表示从第 $i$ 个空间站登陆是否能够完成旅行：

• 如果可以，输出 TAK；
• 否则，输出 NIE。

其中，TAK 在波兰语中表示“是”，NIE 在波兰语中表示“否”。

样例输入

5
3 1
1 2
5 2
0 1
5 4

样例输出

TAK
NIE
TAK
NIE
TAK

数据范围

• $3\le N\le 10^6$；
• 对于所有 $1\le i\le N$，满足 $p_i\ge 0$；
• 对于所有 $1\le i\le N$，满足 $d_i>0$；
• 所有空间站的燃料总量不超过 $2\times 10^9$；
• 所有相邻空间站之间的距离总和不超过 $2\times 10^9$。

来源与许可

本题为 POI 2005 试题「Lot-A Journey to Mars」，题面与测试数据整理自 BZOJ。

样例 1

输入

5
3 1
1 2
5 2
0 1
5 4

输出

TAK
NIE
TAK
NIE
TAK