请注意，本题的内存限制极低（8MB）。

如果存在一个中心点 $(a, b)$ 和两个半径 $L$ 与 $R$（其中 $a, b, L, R$ 为整数，且半径非负），使得集合 $S$ 恰好是所有到 $(a, b)$ 的距离在区间 $(L, R]$ 内的整点集合，则称平面上的整点集合 $S$ 为一个“甜甜圈”（donut）。形式化地，$S = \{(x, y) \in \mathbb{Z} \times \mathbb{Z} : L < \text{dist}((x, y), (a, b)) \le R\}$，其中 $\text{dist}$ 表示标准的平面距离。

我们从空集开始，逐个添加点。请在每次添加点后判断当前集合是否为一个甜甜圈。

第一行包含点的数量 $n$ ($2 \cdot 10^7 \le n \le 2.5 \cdot 10^7$)。接下来的 $n$ 行，每行描述一个添加的点，给出其坐标，中间用空格隔开。所有给定点的坐标均为绝对值不超过 $5000$ 的整数。所有给定的点互不相同。

对于每个添加的点，输出一行，如果添加该点后集合是一个甜甜圈，则输出 “TAK”，否则输出 “NIE”。

样例

输入格式 1

12
4 1
3 2
3 0
2 3
1 0
0 1
1 2
2 -1
2 2
3 1
2 0
1 1

输出格式 1

NIE
NIE
NIE
NIE
NIE
NIE
NIE
TAK
NIE
NIE
NIE
TAK

说明

该样例仅用于解释输入格式，它显然不满足 $n \ge 2 \cdot 10^7$ 的条件（尽管它满足其他所有条件）。你的程序不会在样例测试上进行检查。