Problem G
Cake

Žofka really likes cakes. Her most recent favorite is a rectangular-shaped cake with hard chocolate glazing and white marzipan roses on top. The glazing has been pre-cut in a grid-like pattern at the bakery since this type of glazing is difficult to cut after it hardens. The bakers pride themselves in creating various creations with the roses—they place every rose in the middle of one of the grid squares (at most one rose per square) but the placement differs each time. Žofka invited her friends to share the cake with her—together with her there are as many people as there are roses on the cake as she and each of her friends like a piece with a rose. Žofka can cut only rectangular pieces of the cake along the grid lines. How should she cut the cake so that she and each of her friends gets a rectangular piece with a rose and there is the smallest possible amount of leftover cake?

Figure 1: A possible solution for the sample input. The rectangular pieces cover the cake entirely, so there are no leftovers. This solution is described in the sample output. Note that there are several other correct outputs for the sample input.

Input

The first line contains $p$, $q$, and $n$, where $p \times q$ are the dimensions of the cake and $n$ is the number of roses. Then $n$ lines follow, the $i$-th line contains the coordinates of the $i$-th rose, where the first coordinate is between $1$ and $p$ and the second coordinate is between $1$ and $q$. You may assume that $p$, $q$ and $n$ are at most $10\, 000$.

Output

The output contains $n + 1$ lines. The first $n$ lines contain four numbers each: the $j$-th line contains $a_ j$, $b_ j$, $c_ j$, $d_ j$, where $1 \leq a_ j \leq c_ j \leq p$ and $1 \leq b_ j \leq d_ j \leq q$ and $(a_ j, b_ j)$ and $(c_ j, d_ j)$ correspond to the grid squares at the opposite corners of the rectangular piece for the $j$-th person. The rectangular pieces have to be non-overlapping. The last line contains a single number, the area of the leftovers. The area of the leftovers should be the smallest possible.

4 5 4
2 2
3 4
1 4
4 5

1 1 1 5
2 1 2 5
3 1 3 5
4 1 4 5
0