Problem C
Þarasöfnun

Image from Peter Southwood, taken from Wikimedia Commons

Yet again certain unnamed individuals within KFFÍ are trying to make easy cash and they heard from their engineer friends that anything with sustainable or futuristic in the title gets plenty of grants these days. With this in mind one of them had the idea of building a kelp harvesting robot. Of course they later realized that this was not such an easy task, especially when they had to herd some engineers to actually build the robot itself. This herding went so badly that they completely forgot to finish programming the robot.

Sensors have been placed in the sea where the kelp grows, so the only thing that needs to be done is to get the bot to the right location to harvest the kelp when the sensors send a message. The growing plot can be modeled as a $C \times R$ cell square grid with a plant in each square. The robot starts at $(0, 0)$ at time $0$. The robot can move one square per second in any direction, even diagonally. When a cell is ready for harvesting the robot should always move to that cell along the shortest possible path, always moving diagonally when it helps. The time it takes to harvest the kelp is negligible once the robot arrives at the cell. If several cells are ready to be harvested, the one earliest in the input should always be prioritized. On the other hand, if the robot moves over a cell waiting to be harvested, on its way elsewhere, it should be harvested immediately. If the robot has nothing to do, it is supposed to simply stay still.

Input

The first line of the input contains two positive integers $C, R$, the number of columns and rows of cells in the growing plot. The next line contains a single positive integer $q$, the number of queries. Then there will be $q$ lines, each containing three integers $t$, where $0 \leq t \leq 10^{18}$, $x$, where $0 \leq x < C$, and $y$, where $0 \leq y < R$. $t$ is the time at which the query arrives and $(x, y)$ is the location of the kelp to be harvested. Each location appears at most once in the input, $(x, y) \neq (0, 0)$ and the times are in weakly increasing order.

Output

Print the time of harvest and location in the same format as the input each time a batch of kelp is harvested, in the order they get harvested.

Scoring

5 10
1
1 3 6

7 3 6

10 10
4
1 2 6
2 7 7
3 8 8
4 0 8

7 2 6
12 7 7
13 8 8
21 0 8

9 9
4
2 0 6
4 0 5
10 0 8
11 4 4

7 0 5
8 0 6
12 0 8
16 4 4

5 5
3
0 3 4
0 3 3
0 4 3

3 3 3
4 3 4
5 4 3