Byteazar 决定前往火星，参观那里的空间站。所有的火星空间站都位于一个圆周上。Byteazar 会在其中一个空间站着陆，然后乘坐一种由特殊燃料驱动的交通工具环绕飞行。每升燃料可以让他行驶一米。然而，燃料供应有限，每个空间站提供的燃料量各不相同。Byteazar 可以在他当前所在的空间站加油，但他不能获得超过该处现有燃料量的燃料（他的油箱容量无限）。这些燃料必须足以让他到达下一个空间站。Byteazar 必须决定在哪里着陆，以便他能够访问所有的空间站。最后，他必须回到他着陆的那个空间站。在旅途中，Byteazar 必须沿着圆周行驶，且全程保持两个可能方向中的一个方向不变。

编写一个程序，完成以下任务：

• 从标准输入读取空间站的数量、空间站之间的距离以及每个空间站可用的燃料量；
• 对于每一个空间站，检查 Byteazar 是否可以在那里着陆，即他是否能从该空间站出发，选择一个方向行驶，访问所有空间站并回到出发点；
• 将结果写入标准输出。

输入格式

第一行包含一个整数 $N$ ($3 \le N \le 1,000,000$)，表示火星上空间站的数量。空间站编号从 $1$ 到 $N$。接下来的 $N$ 行描述了所有空间站及其之间的距离。第 $i+1$ 行包含两个整数 $p_i$ 和 $d_i$ ($p_i \ge 0, d_i > 0$)。第一个整数表示第 $i$ 个空间站可用的燃料量（单位：升），第二个整数表示第 $i$ 个空间站与第 $i+1$ 个空间站之间的距离（单位：米）（显然 $d_N$ 表示第 $N$ 个空间站与第 $1$ 个空间站之间的距离）。总可用燃料量以及空间站之间的总距离均不超过 $2,000,000,000$。

输出格式

程序应向标准输出写入 $N$ 行。第 $i$ 行应包含单词 TAK（即波兰语中的“是”），如果 Byteazar 可以在第 $i$ 个空间站着陆，则输出 TAK，否则输出 NIE（即波兰语中的“否”）。

样例

输入 1

5
3 1
1 2
5 2
0 1
5 4

输出 1

TAK
NIE
TAK
NIE
TAK