City Wall

The King of Byteland has lately noticed a sharp drop in the tax revenue collected by his cities. He suspects it is tied to the arrival of dishonest new merchants who most likely slip across the city walls at night to smuggle goods.

The King decides to hire the all-seeing Jacek to climb the church towers each night and watch the city boundaries. Now he wonders whether that is enough: he is not sure that in every city Jacek can see the whole wall from the church tower. Jacek can see all around his head and straight through every building in the city, yet he cannot see a stretch of wall that is hidden behind another stretch of wall. He also cannot see a stretch of wall that lies entirely along his line of sight, because that stretch is then blocked by one of its endpoints (a vertex).

Each city's boundary is a polygon. No city's wall crosses itself, and the church is never on the wall nor outside the city it belongs to.

The first line of standard input contains a single integer $m$ ($1 \le m \le 10$), the number of cities. The descriptions of the cities follow.

The first line of each city's description contains three space-separated integers $n$, $x$, and $y$ ($3 \le n \le 100\,000$, $-10^9 \le x, y \le 10^9$): the number of vertices of that city's wall and the coordinates of its church. Each of the next $n$ lines contains two space-separated integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), the coordinates of the $i$-th wall vertex. The vertices are listed in the order they appear along the wall, so every two consecutive vertices, and the last together with the first, are joined by a wall segment. In tests worth 70% of the points in total, $n \le 3\,500$.

Print exactly $m$ lines. The $i$-th line contains a single word:

• TAK if the whole wall of the $i$-th city is visible from its church tower,
• NIE otherwise.