Background

Polygon Battle is a two-player game.

Problem Description

The game is played on a convex polygon with $n$ vertices. The polygon is divided into $n - 2$ triangles by $n - 3$ diagonals, and these $n - 3$ diagonals intersect at the vertices of the polygon.

One of the triangles is colored black, and the others are white. The two players take turns. On a player's turn, they must cut off one triangle from the polygon along the drawn diagonals. The player who cuts off the black triangle wins.

• Note: A polygon is called a convex polygon if the line segment connecting any two points inside the polygon lies entirely within the polygon.

Input Format

The first line contains an integer $n$, the number of vertices of the polygon. The vertices are numbered clockwise from $0$ to $n - 1$.

The next $n - 2$ lines describe the triangles that form the polygon. In the $(i + 1)$-th line $(1 \le i \le n - 2)$, there are three non-negative integers $a, b, c$ separated by spaces. They are the vertex numbers of the $i$-th triangle. The first given triangle is black.

Output Format

The only line should contain one word:

• TAK, meaning the first player has a winning strategy.
• NIE, meaning the first player does not have a winning strategy.

6

0 1 2

2 4 3

4 2 0

0 5 4

TAK

Hint

For $100\%$ of the testdata, $4 \le n \le 50000$.

Translated by ChatGPT 5