Description

Original source: POI 2004

John plans to drive a car around a circular highway. There are a total of $n$ stations along the highway, each containing a certain amount of gasoline (some stations may have zero fuel). Each liter of gasoline allows the car to travel one kilometer. John must start from one of the stations, travel continuously in either a clockwise or counter-clockwise direction, visit all stations, and return to the starting point. Initially, the car has zero fuel. Upon arriving at each station, John takes all the gasoline available at that station (including the starting station). During the journey, the car must never run out of fuel.

Task: Determine for each station whether John can successfully complete the round trip starting from it.

Input Format

The first line contains an integer $n$, the number of stations on the circular highway.

The next $n$ lines each contain two integers $p_i$ and $d_i$, representing the amount of gasoline stored at the $i$-th station and the distance from the $i$-th station to the next station, respectively.

Output Format

Output $n$ lines. For the $i$-th station, if John can successfully complete the round trip starting from it by traveling continuously in either a clockwise or counter-clockwise direction, output TAK on the $i$-th line; otherwise, output NIE.

Sample 1

5
3 1
1 2
5 2
0 1
5 4

TAK
NIE
TAK
NIE
TAK

Data Range and Hints

For all data, $3\le n\le 10^6$, $0\le p_i\le 2\times 10^9$, and $0\lt d_i\le 2\times 10^9$.