성벽

바이토시아(Bajtocja)의 왕은 최근 도시들이 세금으로 거두는 수입이 크게 줄어든 것을 알게 되었다. 왕은 이것이 도시에 새로 나타난 부정직한 상인들과 관련이 있다고 의심한다. 이들은 밤이 되면 도시의 성벽을 몰래 넘어가 여러 물건을 밀수하는 것으로 보인다.

왕은 무엇이든 꿰뚫어 보는 야체크(Jacek)를 고용하여, 밤마다 교회 탑에 올라가 도시의 경계를 감시하게 하기로 했다. 그런데 왕은 이것만으로 충분한지 확신이 서지 않는다. 모든 도시에서 야체크가 교회 탑 위에서 성벽 전체를 볼 수 있는지 알 수 없기 때문이다. 야체크는 머리 주위 사방을 볼 수 있고 도시의 모든 건물을 관통해서 볼 수 있지만, 성벽의 다른 부분에 가려진 성벽 조각은 볼 수 없다. 또한 자신의 시선 위에 완전히 놓인 성벽 조각도 볼 수 없는데, 그 조각은 성벽의 한 꼭짓점에 가려지기 때문이다.

각 도시의 경계는 다각형 모양이다. 어떤 도시의 성벽도 스스로 교차하지 않으며, 교회는 성벽 위에 있지도 않고 자신이 속한 도시의 경계 밖에 있지도 않다.

표준 입력의 첫째 줄에는 도시의 수를 나타내는 정수 $m$ ($1 \le m \le 10$)이 주어진다. 그 다음 줄부터 각 도시의 정보가 차례로 주어진다.

각 도시 정보의 첫째 줄에는 공백으로 구분된 세 정수 $n$, $x$, $y$ ($3 \le n \le 100\,000$, $-10^9 \le x, y \le 10^9$)가 주어지며, 각각 그 도시 성벽의 꼭짓점 수와 교회의 좌표를 뜻한다. 이어지는 $n$개의 줄에는 각각 공백으로 구분된 두 정수 $x_i$, $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)가 주어지며, 이는 성벽의 $i$번째 꼭짓점 좌표이다. 꼭짓점들은 성벽을 따라 나타나는 순서대로 주어진다. 즉 이웃한 두 꼭짓점, 그리고 마지막 꼭짓점과 첫 꼭짓점은 성벽 선분으로 이어져 있다. 전체 점수의 70%에 해당하는 데이터에서는 $n \le 3\,500$이 성립한다.

정확히 $m$개의 줄을 출력한다. $i$번째 줄에는 한 단어를 출력한다.

• $i$번째 도시에서 교회 탑 위에서 성벽 전체가 보이면 TAK,
• 그렇지 않으면 NIE.