Tapestries

An exhibition of tapestries is opening in a museum of fine arts. Viewed from above, the main exhibition room is a polygon, not necessarily convex. A tapestry hangs on each wall of the room and covers the entire wall.

A lamp has been installed to illuminate the exhibition. It glows uniformly in all directions. Some tapestries have to be flooded with light, while others must not be exposed to strong light.

Your task is to determine whether there is a spot for the lamp that satisfies all of the following:

• Each wall must be either completely illuminated or completely shaded, as required by the tapestry hanging on it. No wall may be partly illuminated and partly shaded.
• If the lamp is located exactly on a wall or on the line extending that wall, that wall is not illuminated.
• The lamp can neither be switched off nor removed from the room. It must be on while located strictly inside the room, so it cannot be placed in a corner or on any wall.

The first line contains a single integer $t$ ($1 \le t \le 20$), the number of data sets. The data sets follow.

Each data set begins with a line containing a single integer $n$ ($3 \le n \le 1000$), the number of walls of the exhibition room. The next $n$ lines describe the room: the $i$-th of them contains two integers $x_i$ and $y_i$ ($-30\,000 \le x_i, y_i \le 30\,000$), the coordinates of the $i$-th vertex of the polygon. The vertices are given in clockwise order.

The following $n$ lines describe the tapestry requirements, one letter per line: S if the wall must be illuminated, or C if it must be shaded. For $1 \le i \le n-1$, the $i$-th of these letters refers to the wall between vertex $i$ and vertex $i+1$, and the last letter refers to the wall between vertex $n$ and vertex $1$.

The polygon has no self-intersections: apart from consecutive sides, which share a common vertex, no two sides share a common point. Moreover, no three vertices are collinear.

For each data set, print a single line containing one word: TAK (Polish for "yes") if the lamp can be placed so that all requirements are met, or NIE (Polish for "no") otherwise.