시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
30 초 8 MB (추가 메모리 없음) 1 1 1 100.000%

문제

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 · 107 ≤ n ¬ 2.5 · 107). 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.

예제 입력 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

노트

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

채점

  • 예제는 채점하지 않는다.