题目描述

题目译自 XX Olimpiada Informatyczna — I etap Gobeliny

Bajtockie 美术博物馆即将举办壁毯展览。主展厅俯视呈多边形（不一定是凸的），每面墙上挂一幅壁毯，覆盖整个墙面。

展厅内放置一盏灯，均匀向四周照明。部分壁毯需充分照明，部分则不可暴露于强光。馆长 Bajtazar 尝试移动灯具位置，却无法满足需求。他忧心忡忡，担心需耗费大量精力重新挂壁毯，而展览开幕在即。你的任务是判断是否存在灯具位置，满足以下条件：

• 每面墙要么全被照亮，要么全被遮暗，依壁毯要求而定；不可有墙部分照亮、部分遮暗。
• 若灯位于墙的直线上，则不照亮该墙。
• 灯不可关闭或移出展厅，须开启并位于厅内（不在墙上或角落）。

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 20)$，表示数据组数。每组数据的格式如下：

• 第一行包含一个整数 $n$ $(3 \leq n \leq 1000)$，表示展厅墙面数。
• 接下来的 $n$ 行，每行两个整数 $x_i, y_i$ $(-30000 \leq x_i, y_i \leq 30000)$，表示多边形顶点坐标，按顺时针顺序。
• 再接下来的 $n$ 行，每行一个字母 S 或 C，分别表示该墙需照亮或遮暗。第 $i$ $(1 \leq i \leq n-1)$ 行对应连接第 $i$ 和第 $i+1$ 顶点的墙，第 $n$ 行对应连接第 $n$ 和第 $1$ 顶点的墙。

展厅多边形无自相交，除相邻边共享端点外，任意两边无公共点。任意三顶点不共线。

输出格式

对每组数据，输出一行包含一个字符串 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

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

NIE
TAK

数据范围与提示

对于 $40\%$ 的数据，$n \leq 20$。
对于 $10\%$ 的数据，所有墙均照亮。