As everyone surely knows, within the administrative borders of Bytocja lies Megabajtocka Island. This island is shaped like a rectangle with height $n$ and width $m$. It is divided into $n \cdot m$ administrative areas in the shape of unit squares, arranged in $n$ rows and $m$ columns. The rows are numbered from north to south with integers from $0$ to $n - 1$, and the columns from west to east with integers from $0$ to $m - 1$. The administrative area at the intersection of the $i$-th row and $j$-th column is denoted by $(i, j)$.

Many years ago, the island was one of the main trade centers, but today it contains only two main port settlements, located in areas with coordinates $(0, 0)$ and $(n - 1, m - 1)$. Land trade is just as important as sea trade, so the existence of a convenient trade route between the settlements—a sequence of administrative areas satisfying the following conditions—is of great importance: the sequence starts at area $(0, 0)$, the sequence ends at area $(n - 1, m - 1)$, every two consecutive areas in the sequence are adjacent by their sides, the sequence contains exactly $n + m - 1$ areas, meaning it is as short as possible, * the sequence does not contain areas occupied by enemy strongholds, more on which in a moment!

The strategic location on the Gigabajtowe Sea makes Megabajtocka Island an attractive target for the enemies of Bytocja, who plan to invade the island and start building their strongholds on it. Thanks to air support, they can appear anywhere, not just at the shore!

Fortunately, Bytocja has a secret weapon, a special unit called Bajtogrom. If, after building an enemy stronghold, a convenient trade route between the port settlements ceases to exist (and only in this case!), the soldiers of Bajtogrom immediately enter the action and, in the blink of an eye, pacify the newly built stronghold, leaving only a scorched ruin behind.

The fate of all of Bytocja (or at least Megabajtocka Island) is in your hands! Given the sequence of areas where enemy strongholds are being built, you must determine which of them should be immediately destroyed by Bajtogrom.

The enemy has not yet established a precise attack plan. Interestingly, the location of each subsequent stronghold depends on which of the previous attempts ended with an intervention by Bajtogrom. The enemy maintains a value $x$, initially equal to $0$. In the $i$-th step, a stronghold will be created in the area $$((r_i \oplus x) \mod n, (c_i \oplus x) \mod m),$$ and a possible armed reaction by Bajtogrom will cause the value of $x$ to change to $x \oplus z_i$. The operation $\oplus$ in the formulas above denotes the exclusive OR, also known as xor.

You may assume that the enemy will never attempt to build a stronghold in an area with a port settlement, an existing stronghold, or a ruin left by a destroyed stronghold. In other words, the decoded sequence of areas contains no repetitions and does not include the fields $(0, 0)$ or $(n - 1, m - 1)$.

Input

The first line of input contains three integers $n$, $m$, and $k$ ($2 \le n, m \le 100\,000$, $1 \le k \le 1\,000\,000$), representing the dimensions of Megabajtocka Island and the number of strongholds the enemy state will build, respectively. Each of the next $k$ lines contains three integers $r_i, c_i, z_i$ ($0 \le r_i, c_i, z_i < 2^{20}$), representing the values needed to determine the location of the $i$-th stronghold and update the value of $x$ in case of an intervention by Bajtogrom.

Output

The output should contain $k$ lines, each containing a single word TAK or NIE, depending on whether Bajtogrom should intervene in connection with the newly built stronghold.

Examples

Input 1

3 5 7
0 1 123
1 0 0
4 8 0
2 2 16
2 3 0
18 19 17
3 0 0

Output 1

NIE
TAK
NIE
TAK
NIE
TAK
NIE

Note

Explanation of the example: The enemy state builds strongholds sequentially in areas $(0, 1)$, $(1, 0)$, $(1, 3)$, $(2, 2)$, $(0, 4)$, $(2, 3)$, and $(2, 1)$. The figure shows all strongholds, with the destroyed ones having a dashed border. We see that at the end, a convenient trade route still exists.

Let's look at where the decoded coordinates came from. Remember that non-destroyed strongholds do not modify the value of $x$. Destroying the second stronghold does not change the value of $x$, because $z_2 = 0$, but it gets more interesting later. Destroying the fourth stronghold in area $(2, 2)$ changes the value of $x$ from $0$ to $16$, so immediately after that $(r_5, c_5) = (2, 3)$ must be decoded as $$((2 \oplus 16) \mod n, (3 \oplus 16) \mod m) = (18 \mod n, 19 \mod m) = (0, 4).$$ * Next, $(r_6, c_6) = (18, 19)$ gives the coordinates of the sixth stronghold $$((18 \oplus 16) \mod n, (19 \oplus 16) \mod m) = (2, 3).$$ This one must also be destroyed, so we change $x$ to $x \oplus z_6 = 16 \oplus 17 = 1$. * We use the new value $x = 1$ to decode the coordinates of the last, seventh stronghold as $$((3 \oplus 1) \mod n, (0 \oplus 1) \mod m) = (2, 1).$$

Subtasks

In tests worth 5 points, the additional condition $n \cdot m \le 25\,000\,000$ holds.