题目背景

Source: AMPPZ 2019.

请注意本题特殊的内存限制（8 MB）。

题目描述

平面上的一个整数坐标点集 $S$ 被称为甜甜圈，如果存在一个中点 $(a, b)$ 和两个半径 $L$ 和 $R$（其中 $a, b, L, R$ 为整数且半径非负），使得 $S$ 恰好是所有与 $(a, b)$ 的距离落在区间 $(L, R]$ 内的点的集合。形式化定义为：

$$S = \{(x, y) \in \mathbb{Z} \times \mathbb{Z} : L < \text{dist}((x, y), (a, b)) \leq R\}, $$

其中 $\text{dist}$ 表示欧几里得距离。

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

请注意本题特殊的内存限制（8 MB）。

输入格式

本题单个测试点内有多组测试数据。

输入的第一行包含点的数量 $n$（$2 \cdot 10^7 \leq n \leq 2.5 \cdot 10^7$）。接下来的 $n$ 行每行描述一个添加的点，坐标由单个空格分隔。坐标是绝对值不超过 5000 的整数。所有给定的点互不相同。

输出格式

对于每个点，输出一行 $\texttt{TAK}$（如果添加该点后集合是一个甜甜圈）或 $\texttt{NIE}$（如果不是）。

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

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

提示

样例解释：该示例仅用于解释输入格式，显然不满足 $n \geq 2 \cdot 10^7$ 的条件（但满足其他所有条件）。实际测试点中不包含这组数据。