# Internet Problem Solving Contest

## Problem H – Harvesting potatoes

There is a rectangular ﬁeld divided into r × c square cells.

Potatoes grow on all cells of the ﬁeld. You have a potato harvester and want to harvest all of them. A potato harvester is basically a large car equipped with mechanical spades and other stuﬀ necessary to get the potatoes from the soil to the back of the car. The driver has a switch that turns the mechanical spades on and oﬀ.

The harvester operates in passes. In each pass it traverses either a single row or a single column of the ﬁeld, starting at one border and ending at the opposite one. The capacity of the harvester is limited: in each pass it can only harvest at most d cells. These can be any of the cells it passes through. In this task your goal will be to produce a harvesting schedule that uses the smallest number of passes.

In practice there is one more factor: harvester drivers are bad at following complicated instructions. Harvesting contiguous segments is much simpler than repeatedly turning the spades oﬀ and on again at the right places. The diﬃculty of a given pass can be measured as the number of times the driver has to ﬂip the switch during the pass. In other words, the diﬃculty is twice the number of contiguous segments of cells harvested in that pass. (Note: The driver must harvest each cell exactly once. It is not allowed to leave the spades on while the harvester passes over already harvested cells, as this damages the soil.)

The diﬃculty of a schedule is the diﬃculty of the most complicated pass it contains, i.e., the maximum over all diﬃculties of individual passes.

Problem speciﬁcation

You will be given the dimensions r and c and the capacity d. For the easy data set H1 your task is to produce any harvesting schedule with the smallest number of passes. For the hard data set H2 your task is to produce any harvesting schedule that solves the easy data set and additionally has the smallest possible diﬃculty (out of all such schedules).

Input speciﬁcation

The ﬁrst line of the input ﬁle contains an integer t specifying the number of test cases. Each test case is preceded by a blank line. Each test case is given as a single line with three integers: r, c, and d.

Each test case in the easy data set has r,c 12. Each test case in the hard data set has r,c 400.

Output speciﬁcation

For each test case, output r rows, each containing c space-separated positive integers. These represent the harvesting schedule. More precisely, each integer gives the number of the pass in which the particular cell is harvested. (Additional whitespace is OK as long as the number of tokens in your output is correct.)

Example

input
2

2 9 5

3 5 2
output
1 1 1 1 1 2 2 2 2
3 3 3 3 3 4 4 4 4

1 2 3 4 5
1 2 3 4 5
6 6 7 8 7

The ﬁrst test case: The cells are harvested in rows. The second test case: We ﬁrst do one pass in each column and then three passes in the last row. The output shows a schedule that is shortest but does not have the smallest possible diﬃculty – to ﬁx that, swap the 8 with one of the 7s.