Problem D. Divide by Squares ≡

Author:	Южно-Уральский открытый командный чемпионат		Time limit:	5 sec
Input file:	input.txt		Memory limit:	64 Mb
Output file:	output.txt

Statement

Divide by Squares is played on a rectangular grid. Some of the squares in the grid are numbered. The objective is to divide the grid into rectangular and square pieces such that each piece contains exactly one number, and that number represents the area of the rectangle (from Wikipedia).

On the pictures you can see a sample of the puzzle and its solution.

You are to write program that solves this puzzle.

Input file format

The first line of the input file contains three integers, separated by spaces — the height H, the width W of the grid, and total amount K of numbers on the grid. Each of the next K lines contains three integers, separated by spaces — position (i, j) of the number and the number itself. The puzzle in the input has at least one solution.

Output file format

The output file must contain K lines. For each number in the input you should print four integers on corresponding line — coordinates of left upper corner of the rectangle that contains this number and its height and width. You have to print arbitrary solution.

Constraints

1 ≤ H ≤ 10, 1 ≤ W ≤ 10, 1 ≤ K ≤ W * H

Sample tests

No.	Input file (input.txt)	Output file (output.txt)
1	4 4 4 2 1 4 2 3 6 3 1 4 4 4 2	1 1 2 2 1 3 3 2 3 1 2 2 4 3 1 2

---