P3548 [POI 2013] GOB-Tapestries

Byteotian 美术馆正在举办一场挂毯展览。 从顶部看，主展厅是一个多边形（不一定是凸形）。房间的每一面墙上都挂着一幅挂毯，每幅挂毯都占据了墙壁的全部面积。 为了照亮展览，房间里安装了一盏灯，这盏灯向各个方向均匀发光。然而，有些挂毯必须充满光线，但另一些挂毯不能暴露在强光下。 策展人 Byteasar 一直在房间里移动灯，但到目前为止，他对结果并不满意。 现在，他对移动挂毯的前景感到恐惧——这需要付出很多努力，展览很快就会开幕。 也许你能告诉他，他的尝试是否注定要失败？ **你的任务**是确定是否有这样一个点，将灯放在其中满足以下条件： 1. 根据挂在墙上的挂毯的要求，每面墙要么完全照亮，要么完全遮阳； 2. 不可能有一面墙是部分照明和部分遮阳的；如果灯正好位于墙上或其延伸部分，则这面墙不会被照亮； 3. 灯既不能关闭，也不能从房间里拿走；它必须严格位于房间内（即它不能放置在角落或任何墙上）。

标准输入的第一行中有一个整数 $T$，表示数据集的数量。 对于每个数据集，第一行有一个整数 $N$，表示主展厅的墙的数量。 接下来 $N$ 行，每行 $2$ 个用空格隔开的整数 $x_i$ 和 $y_i$，表示房间角落的坐标。换句话说，就是相应多边形的顶点。顶点按顺时针方向给出。 然后的的 $N$ 行指定了挂毯的要求。每一行都包含一个字母 $S$ 或 $C$，分别表示墙壁必须被照亮或遮蔽。 第 $i$（$1\le i\le N$）行中的字母表示第 $i$ 个顶点和第 $i+1$ 个顶点之间的墙，最后一行中的字母表示最后一个顶点和第一个顶点之间的墙。 描绘房间形状的多边形没有自交，即除了连续的边共享一个共同的顶点外，多边形的任何两条边都不共享一个顶点。而且没有三个顶点在一条线上。

对于每个数据集，你的程序应该在标准输出中打印一行包含一个单词：如果灯可以满足以上要求则输出 `TAK`（波兰语中“是”的意思）,否则输出 `NIE`（波兰语中表示“否”的意思）。

- 对于 $40\%$ 的数据点，$n\le20$。 - 对于另外 $10\%$ 的数据点，所有地毯都需要被照亮。 - 对于 $100\%$ 的数据点，满足 $1\le T\le 20$，$3\le N\le 1000$，$-30000\le xi,yi\le30000$。