P12813 [AMPPZ 2019] Donuts

**Time limit:** 30s, **memory limit:** 8MB. **Please note an exceptionally low memory limit (8MB) for this problem.**

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.**

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.

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.

**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.