Description

A set $S$ of integer coordinate points in a plane is a donut, if there exists a midpoint $(a, b)$ and two radii $L$ and $R$ (with integer $a, b, L, R$ and non-negative radii) such that $S$ is precisely the set of all points whose distance from $(a, b)$ is in the interval $(L, R]$. Formally,

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

where $\text{dist}$ denotes standard plane distance.

We begin with an empty set and add points one by one. Determine, after every added point, if the set is currently a donut.

Please note an exceptionally low memory limit (8MB) for this problem.

Input Format

The first line of input contains the number of points $n$ ($2 \cdot 10^7 \leq n \leq 2.5 \cdot 10^7$). Each of the next $n$ lines describes a single added point, giving its coordinates separated by a single space. The coordinates are integers of absolute value not greater than 5000. All the given points are distinct.

Output Format

For every point output (in a separate line) $\texttt{TAK}$, if after adding this point the set is a donut, and $\texttt{NIE}$, if it isn’t.

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

Hint

Example: The example is given only for explaining the input format, and it obviously does not satisfy the $n \geq 2 \cdot 10^7$ condition (though it satisfies all the others). Your program will not be checked on the example test.