태피스트리

한 미술관에서 태피스트리 전시회가 열린다. 위에서 내려다본 주 전시실은 볼록하지 않을 수도 있는 다각형이다. 전시실의 각 벽에는 태피스트리가 한 점씩 걸려 있으며, 태피스트리는 벽 전체를 덮는다.

전시를 밝히기 위해 램프 하나를 설치했다. 램프는 모든 방향으로 균일하게 빛을 낸다. 어떤 태피스트리는 빛을 충분히 받아야 하고, 어떤 태피스트리는 강한 빛에 노출되면 안 된다.

다음 조건을 모두 만족하도록 램프를 놓을 수 있는 위치가 있는지 판정하여라.

• 각 벽은 걸린 태피스트리의 요구에 따라 완전히 밝거나 완전히 그늘져야 한다. 일부만 밝고 일부만 그늘진 벽이 있어서는 안 된다.
• 램프가 어떤 벽 위, 또는 그 벽을 연장한 직선 위에 정확히 놓이면 그 벽은 밝지 않은 것으로 본다.
• 램프는 끌 수도 없고 방 밖으로 뺄 수도 없다. 램프는 반드시 방의 엄격한 내부(경계는 포함하지 않는다)에 놓여야 하며, 꼭짓점이나 벽 위에는 놓을 수 없다.

첫째 줄에 데이터 집합의 수를 나타내는 정수 $t$ ($1 \le t \le 20$)가 주어진다. 이어서 각 데이터 집합이 주어진다.

각 데이터 집합의 첫 줄에는 전시실의 벽 개수를 나타내는 정수 $n$ ($3 \le n \le 1000$)이 주어진다. 다음 $n$개의 줄에는 다각형의 꼭짓점 좌표가 주어지며, $i$번째 줄에는 두 정수 $x_i$와 $y_i$ ($-30\,000 \le x_i, y_i \le 30\,000$)가 주어진다. 꼭짓점은 시계 방향 순서로 주어진다.

그 다음 $n$개의 줄에는 각 벽의 요구 사항이 한 줄에 한 글자씩 주어진다. 밝아야 하면 S, 그늘져야 하면 C이다. $1 \le i \le n-1$에 대해 $i$번째 글자는 $i$번 꼭짓점과 $i+1$번 꼭짓점 사이의 벽을 나타내고, 마지막 글자는 $n$번 꼭짓점과 $1$번 꼭짓점 사이의 벽을 나타낸다.

다각형은 자기 자신과 교차하지 않는다. 즉, 공통 꼭짓점을 가지는 이웃한 변을 제외하면 어떤 두 변도 공통점을 가지지 않는다. 또한 어떤 세 꼭짓점도 한 직선 위에 있지 않다.

각 데이터 집합에 대해 한 줄에 한 단어를 출력한다. 모든 요구 사항을 만족하도록 램프를 놓을 수 있으면 TAK("예"를 뜻하는 폴란드어), 그렇지 않으면 NIE("아니오"를 뜻하는 폴란드어)를 출력한다.