[POI2013] GOB-Tapestries

An exhibition of tapestries is opening in Byteotian Museum of Fine Arts. The main exhibition room, viewed from top, is a polygon (not necessarily convex). A tapestry is hanged on each wall of the room, each tapestry taking all the area of its wall. A lamp has been installed in the room in order to illuminate the exhibition. The lamp is glowing uniformly in all directions. However, while some of the tapestries have to be flooded with light, others cannot be exposed to strong light. Byteasar, the curator, has been moving the lamp around the room, but so far he is not satisfied with the results. Now he is terrified by the prospect of moving the tapestries around instead - this would require much effort, and the exhibition is to open soon. Perhaps you will be able to tell him if his attempts are doomed or not? Your task is to determine if there is such a spot that placing the lamp in it satisfies the following: each wall is to be either completely illuminated or completely shaded, as required by the tapestry hanging on it; there can be no wall that is partly illuminated and partly shaded; if the lamp is located exactly on the wall or its extension, this wall is not illuminated; the lamp can neither be switched off nor taken away from the room; it has to be on while located (strictly) inside the room (i.e., it cannot be placed in a corner or on any wall). 一个挂毯的艺术展览在Byteotian优秀艺术品博物馆展开！ 主展室的俯视图是一个多边形（不一定是凸的）。房间的每面墙壁上都挂着一个挂毯，每个挂毯都占据了所在墙的全部面积。 一盏灯被安装在房间内以照亮展览品，灯对于所有方向发的光都是均匀的。 然而有些挂毯需要被光照亮，其他的却必须避开强光。 策展人Byteasar，一直在房间里移动灯，但到目前为止，他一直没得出满意的结果。 现在展览即将开放，面对自己捉急的智商，他被水淹没，不知所措。 于是他找来了你，而你需要找出究竟有没有这样一个合适的地方挂灯来满足以下条件： 每堵墙要么完全被照亮，要么被完全遮蔽；因为地毯对光照是十分挑剔的，所以不能有某堵墙被部分照亮/遮蔽；如果灯被安在某堵墙的延长线上，这堵墙不会被照亮；灯既不能被熄灭，也不能移动位置，必须严格固定在房间一个确定的位置上（既不能安角落也不能安墙上）。 输入格式： 第一行是一个整数t(1<=t<=20)，代表有t组数据。 每组数据如下： 第一行是一个整数n(3<=n<=1000)代表展厅里的墙数。 下面的n行指定房间的形状： 每行包括一对整形xi和yi(-30000<=xi,yi<=30000;i=1,2,...n)他们之间被一个空格隔开，对应房间（多边形）顶点的坐标，顶点坐标按顺时针排列。 下面的n行指定了每个墙上挂毯的光照需求： 每行为一个字母S或C，分别代表挂毯需要被照亮或遮蔽。 第i块挂毯（1<=i<=n-1）被挂在第i堵墙和第i+1堵墙。 最后一块挂毯被挂在第一堵墙和最后一堵墙之间。 顶点构成的多边形没有交叉点，也就是说除了连续的边共用一个顶点之外，没有任意两个多边形的边共用一个顶点。而且多边形没有任何三个点共线。 输出格式： 对于每一组数据，你的程序都应该输出一个包含一个单词的单行的标准输出： 如果灯可以放置以满足上述所有要求，输出"TAK"（波兰语的yes），反之输出"NIE"（波兰语的no） 提示： 对于40%的数据点，n<=20; 对于另外10%的数据点，所有地毯都需要被照亮。

There is a single integer  () in the first line of the standard input, denoting the number of data sets. The following lines describe these data sets. The first line of a single description holds a single integer  (), denoting the number of walls in the main exhibition room. Then the following  lines specify the room's shape. Each of those lines contains a pair of integers  and  ( for ), separated by a single space, denoting the coordinates of the room's corner or, in other words, the vertex of corresponding polygon. The vertices are given clockwise. The next  lines specify the tapestries' requirements. Each of those lines contains a single letter, S or C, denoting that the wall has to be illuminated or shaded, respectively. The letter in the -th of these lines (for ) regards the wall between the -th and the -th vertex. The letter in the last of these lines regards the wall between the last and the first vertex. The polygon depicting the room's shape has no self-crossings, i.e., with the exception of successive sides, which share a common vertex, no two sides of the polygon share a common point. Furthermore, no three vertices …

For each data set your program should print to the standard output a single line containing a single word: TAK (Polish for yes) if the lamp can be placed so as to satisfy all aforementioned requirements, or NIE (Polish for no) otherwise.

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