Byteotian 美术馆正在举办一场挂毯展览。从上方俯瞰，主展厅是一个多边形（不一定是凸多边形）。每面墙上都挂着一幅挂毯，每幅挂毯覆盖了其所在墙面的全部区域。

为了照亮展览，展厅内安装了一盏灯。这盏灯向各个方向均匀发光。然而，有些挂毯需要被光照亮，而另一些则不能暴露在强光下。

馆长 Byteasar 已经在展厅里四处移动过这盏灯，但到目前为止，他对结果并不满意。现在，他一想到要移动挂毯就感到恐惧——那需要耗费巨大的精力，而且展览很快就要开幕了。也许你能告诉他，他的尝试是否注定会失败？

你的任务是确定是否存在这样一个位置，将灯放置在此处可以满足以下条件：

• 每面墙要么被完全照亮，要么被完全遮蔽，具体取决于挂在墙上的挂毯的要求；不存在既有部分被照亮又有部分被遮蔽的墙。
• 如果灯恰好位于某面墙或其延长线上，则该墙不被照亮。
• 灯不能被关闭，也不能移出展厅；它必须在位于展厅（严格）内部时开启（即它不能被放置在角落或任何墙面上）。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 20$)，表示数据集的数量。接下来是这些数据集的描述。

每个数据集的第一行包含一个整数 $n$ ($3 \le n \le 1\,000$)，表示主展厅的墙壁数量。接下来的 $n$ 行描述了展厅的形状。每行包含一对整数 $x_i$ 和 $y_i$ ($-30\,000 \le x_i, y_i \le 30\,000$，对于 $i=1, 2, \dots, n$)，由空格分隔，表示展厅的角点坐标，即对应多边形的顶点。顶点按顺时针顺序给出。

接下来的 $n$ 行指定了挂毯的要求。每行包含一个字母 S 或 C，分别表示该墙面需要被照亮（Shaded，此处指被光照亮）或遮蔽（Covered，此处指避光）。第 $i$ 行（对于 $1 \le i \le n-1$）的字母对应第 $i$ 个顶点与第 $i+1$ 个顶点之间的墙面。最后一行对应的字母是最后一个顶点与第一个顶点之间的墙面。

描述展厅形状的多边形没有自交，即除了相邻边共享一个公共顶点外，多边形的任意两条边没有公共点。此外，多边形的任意三个顶点不共线。

输出格式

对于每个数据集，程序应在标准输出中打印一行，包含一个单词：

• TAK（波兰语，意为“是”），如果灯可以放置在满足上述所有要求的位置；
• NIE（波兰语，意为“否”），否则。

样例

输入格式 1

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

输出格式 1

TAK

输入格式 2

2
3
0 0
0 1
1 0
S
C
S
3
0 0
0 1
1 0
S
S
S

输出格式 2

NIE
TAK