Lamp and Tapestries

An exhibition of tapestries is opening in the Byteotian Museum of Fine Arts. The main exhibition room has the shape of a polygon (which may be non‐convex). A tapestry is hung on each wall – each covering the full length of its wall. A lamp inside the room glows uniformly in all directions. However, some tapestries must be flooded with light while others must be kept in the shade.

Once the curator, Byteasar, tried moving the lamp around the room but he couldn’t achieve the desired effect. Now, with the exhibition looming, he is considering moving the tapestries instead – a laborious task. He asks you to decide whether there exists a position inside the room (strictly in the interior, i.e. not on any wall or vertex) at which the lamp can be placed so that each wall is either completely illuminated or completely in shadow as required by the tapestry hanging on it.

The following physical model is assumed. Consider a wall given by its endpoints A and B. Let \(\vec{d} = B-A\) and let \(D = \|\vec{d}\|^2\). When a point lamp L is placed in the room (and not on the line through A and B or its extension) its light falls on the wall in the following way. If \(X\) is the foot of the perpendicular from L onto the line through A and B then the set of points of the wall illuminated by the lamp is exactly the open half‐line of the line that starts at \(X\) and goes in the direction of L. In particular, the wall is completely illuminated if and only if the entire segment \(AB\) lies in that half–line, and it is completely in shadow if and only if \(AB\) lies in the complementary half–line. (Note that if the lamp lies exactly on the wall or on its extension then the wall is not illuminated at all.)

Each wall has a requirement: if the corresponding letter is S then the tapestry must be illuminated (which happens exactly when the entire wall is hit by light), and if the letter is C then the tapestry must remain in shadow. Under the physical model the conditions can be stated by means of the scalar product. For a wall with endpoints A and B (with \(\vec{d} = B-A\) and \(D=\|\vec{d}\|^2\)) and a lamp at L, define \(R = \vec{d}\cdot (L-A)\). Then:

• If the tapestry is to be illuminated (S), then
  either \(R \le 0\) or \(R \ge D\).
• If the tapestry is to be in shadow (C), then
  \(0 < R < D\).

Your task is to decide whether there exists a point L strictly inside the polygon such that for every wall the corresponding inequality holds.

inputFormat

The input begins with an integer \(t\) (\(1 \le t \le 20\)), the number of test cases. Each test case has the following format:

1. An integer \(n\) (\(3 \le n \le 1000\)) representing the number of walls (and vertices) of the room.
2. Then follow \(n\) lines. Each line contains two integers \(x_i\) and \(y_i\) (\(-30000 \le x_i,y_i \le 30000\)). These are the coordinates of the vertices of the polygon in clockwise order.
3. Then follow \(n\) lines. Each line contains a single character, either S or C. The ith line specifies the light requirement for the tapestry hung on the ith wall. (A letter S means the wall must be completely illuminated while C means it must be completely in shadow.)

outputFormat

For each test case, output a single line containing a single word: TAK if there exists a valid placement of the lamp meeting all the requirements, or NIE otherwise.

sample

1
3
0 0
10 0
0 10
C
C
C

TAK