P3422 [POI 2005] LOT-A Journey to Mars

题目描述

圆圈上有 $n$ 个点（编号为 1 ～ n），一辆汽车 可选 任意一点 开始绕圈旅行。

第 $i$ 个点的可补充的油量为 $p_i$升，与点 1 的距离为 $d_i$ 米 。

一升油只能跑 $1$ 米，汽车的油箱容量无限。

判断汽车从个点出发绕圈（顺时针或逆时针）回到出发点是否可行。

输入格式

第一行一个整数 $n \ (3\le n \le 10^6)$。

下来 $n$ 行，每行两个整数 $p_i \ \ d_i \ \ ( p_i \ge 0 ， d_i > 0 ，\sum d_i \le 2\times10^9)$。

输出格式

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

若在点 $i$ 出发是可行的，则需要在第 $i$ 行输出 TAK，否则输出 NIE。

输入输出样例 #1

输入 #1

5
3 1
1 2
5 2
0 1
5 4

输出 #1

TAK
NIE
TAK
NIE
TAK