Problem Background

Bajtel specializes in manufacturing integrated circuit boards.

Due to the large amount of data, another part of Subtask 1 has been moved here.

Problem Description

Bajtel produces integrated circuit boards of size $n \times m$, with the powered grid being $(1,1)$.

We can connect two adjacent grids with a circuit to allow electricity to flow from one grid to another. Several circuits form an integrated circuit.

Now, we need to connect $n \times m-1$ circuits, and we require the longest integrated circuit to be exactly $k$ in length, and all grids must be powered.

Find a way to connect the circuits.

Input Format

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

Output Format

If there is no way to connect the circuits that meets the requirements, output the string NIE and end the program.

If there is a way to connect the circuits that meets the requirements:
- The first line should be the string TAK.
- The next $n \times m-1$ lines should each contain four integers $u_1, v_1, u_2, v_2$ representing a circuit connection between $(u_1, v_1)$ and $(u_2, v_2)$.

If there are multiple solutions, output any one of them.

Sample Input and Output

Sample Input #1

2 3 4

Sample Output #1

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

Sample Input #2

2 3 1

Sample Output #2

NIE

Sample Input #3

2 3 3

Sample Output #3

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

Sample Input #4

1 10 10

Sample Output #4

NIE

Notes

Sample Explanation

For Sample 1, as shown in the following diagram:

Additional sample cases can be found in the sample.zip file in the supplementary materials.

Data Size and Constraints

This problem uses subtask-based scoring.

• 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 there is indeed a solution for this data point) but make a mistake in the description of the circuit connections, you can still receive $20\%$ of the points.

Notes

Translated from POI 2019 E Integrated Circuit.

见题面 Input 部分

见题面 Output 部分