Description

Byteotian 美术馆正在举办一场挂毯展览。

从顶部看，主展厅是一个多边形（不一定是凸形）。房间的每一面墙上都挂着一幅挂毯，每幅挂毯都占据了墙壁的全部面积。

为了照亮展览，房间里安装了一盏灯，这盏灯向各个方向均匀发光。然而，有些挂毯必须充满光线，但另一些挂毯不能暴露在强光下。

策展人 Byteasar 一直在房间里移动灯，但到目前为止，他对结果并不满意。

现在，他对移动挂毯的前景感到恐惧——这需要付出很多努力，展览很快就会开幕。

也许你能告诉他，他的尝试是否注定要失败？

你的任务是确定是否有这样一个点，将灯放在其中满足以下条件：

1. 根据挂在墙上的挂毯的要求，每面墙要么完全照亮，要么完全遮阳；
2. 不可能有一面墙是部分照明和部分遮阳的；如果灯正好位于墙上或其延伸部分，则这面墙不会被照亮；
3. 灯既不能关闭，也不能从房间里拿走；它必须严格位于房间内（即它不能放置在角落或任何墙上）。

Input Format

标准输入的第一行中有一个整数 $T$，表示数据集的数量。

对于每个数据集，第一行有一个整数 $N$，表示主展厅的墙的数量。

接下来 $N$ 行，每行 $2$ 个用空格隔开的整数 $x_i$ 和 $y_i$，表示房间角落的坐标。换句话说，就是相应多边形的顶点。顶点按顺时针方向给出。

然后的的 $N$ 行指定了挂毯的要求。每一行都包含一个字母 $S$ 或 $C$，分别表示墙壁必须被照亮或遮蔽。

第 $i$（$1\le i\le N$）行中的字母表示第 $i$ 个顶点和第 $i+1$ 个顶点之间的墙，最后一行中的字母表示最后一个顶点和第一个顶点之间的墙。

描绘房间形状的多边形没有自交，即除了连续的边共享一个共同的顶点外，多边形的任何两条边都不共享一个顶点。而且没有三个顶点在一条线上。

Output Format

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

1
16
5 -3
4 -4
3 -7
0 -5
-3 -7
-4 -4
-5 -3
-1 -1
-4 3
-2 4
-1 2
0 7
1 2
2 4
4 3
1 -1
C
S
S
S
S
C
C
S
S
C
S
S
C
S
S
C
        

TAK

Hint

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