18053번 - Donuts 다국어

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) ∈ Z × Z : L < dist((x, y), (a, b)) ≤ R}, where 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 · 10⁷ ≤ n ¬ 2.5 · 10⁷). 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) TAK, if after adding this point the set is a donut, and NIE, if it isn’t.

The example is given only for explaining the input format, and it obviously does not satisfy the n ≥ 2 · 10⁷ condition (though it satisfies all the others). Your program will not be checked on the example test.