P6663 [POI 2019/2020 R1] Układ scalony / Integrated Circuit

Bajtel Company specializes in producing integrated circuit boards.

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.

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

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.

#### 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](https://sio2.mimuw.edu.pl/c/oi27-1/dashboard/) E [Układ scalony](https://sio2.mimuw.edu.pl/c/oi27-1/p/ukl/). Translated by ChatGPT 5