Description

Source Problem: POI XXVII - I etap (Układ scalony)

A new integrated circuit being developed by the Bytel company has $n \cdot m$ memory chips arranged in $n$ rows and $m$ columns. The chip in the $i$-th row and $j$-th column (for $1 \leq i \leq n, 1 \leq j \leq m)$ has coordinates $(i,~j)$.

The chip in upper left corner, with coordinates $(1,~1)$, is supplied with power. To feed the remaining chips with power, $nm−1$ further connections have to be made. Specifically, each chip should be connected to at least one of the adjacent chips on its left, right, top or bottom so that there exists a route connecting it with the chip in the upper left corner. The company’s electrical engineers insist that the longest path (between some pair of chips) in the connection network must have length exactly $k$ lest quantum effects render the circuit useless.

Write a program that will find such a connection network if it exists.

Input Format

In the first and only input line, there are three integers $n$, $m$, and $k$ which specify the circuit’s parameters: number of rows and columns, as well as desired length of the longest path.

Output Format

If there is no network with the desired properties, then the single word NIE (Polish for no) should be printed to the output.

Otherwise, $nm$ lines should be printed, the first one consisting of the word TAK (Polish for yes), and each of the following $nm − 1$ lines containing four integers $i1, j1, i2, j2$, separated by single spaces, which indicate that the network contains the connection between chips with coordinates $(i1, j1)$ and $(i2, j2)$.

Should more than one correct solution exist, your program may report any of those.

Sample 1

2 3 4

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

A sample connection network is depicted for the $2 \times 3$ integrated chip. The longest path connects the chips with coordinates $(2,~1)$ and $(2,~3)$, and has a length of $4$.

2 3 1

NIE

Additional Samples

• Additional Sample 1: $n = 2, m = 3, k = 3$;

• Additional Sample 2: $n = 1, m = 10, k = 10$;

• Additional Sample 3: $n = 1000, m = 1000, k = 999 999$.

Constraints

The set of tests consists of the following subsets. Within each subset, there may be several tests.

Your program will be awarded $20\%$ of the score for each test where it correctly prints TAK to the first output line but then prints an incorrect network scheme.

For all test data, it is guaranteed that $1 \le n, m \le 1000, 0 \le k \le 10^6$.