Background

Bajtel Company specializes in producing integrated circuit boards.

Problem Description

The integrated circuit board produced by Bajtel Company has size $n \times m$, and the cell that is powered at the beginning is $(1,1)$.

We can connect a wire between two adjacent cells so that electricity can flow from one cell to the other. Several wires form an integrated circuit.

Now we need to connect $n \times m - 1$ wires, and require that the longest integrated circuit has length exactly $k$, and also require that all cells are powered.

Find one way to connect the wires.

Input Format

One line with three integers $n, m, k$, representing the board size and the required length of the longest integrated circuit.

Output Format

If there is no wiring method that satisfies the statement, output a string NIE and terminate.

If there exists a wiring method that satisfies the statement:
Output one string TAK on the first line.
Then output $n \times m - 1$ lines, each with four integers $u_1, v_1, u_2, v_2$, meaning there is a wire connecting $(u_1, v_1)$ and $(u_2, v_2)$.
If there are multiple valid solutions, output any one.

2 3 4

TAK
1 1 1 2
1 1 2 1
1 2 2 2
2 3 2 2
1 2 1 3

2 3 1

NIE

2 3 3 

TAK
1 2 2 2
1 1 1 2
2 2 2 3
1 2 1 3
2 2 2 1

1 10 10

NIE

Hint

Sample Explanation

For sample $1$, as shown in the figure below.

Another additional sample set can be found in the attached file sample.zip.

Constraints

This problem uses bundled testdata.

• Subtask 1 (20 pts): $n, m \le 6$.
• Subtask 2 (20 pts): $n \le 3$.
• Subtask 3 (30 pts): $n \times m$ is odd.
• Subtask 4 (30 pts): $n \times m$ is even.

For $100\%$ of the data, $1 \le n, m \le 1000$, $0 \le k \le 10^6$.

If you output TAK (and this test case indeed has a solution), but you make mistakes in the wiring description afterward (while still keeping the output format valid), you can get $20\%$ of the score.

Note

Translated from POI 2019 E Układ scalony.

Translated by ChatGPT 5