Problem Description

There is a large grassland divided into $n$ rows and $m$ columns. In the sky above this grassland, there are $k$ balloons. The $i$-th balloon is located above the $x_i$-th row and $y_i$-th column, at a height $h_i$ from the ground, and its color is $c_i$.

From a position, one can only see the balloon directly above that position, which is the closest to the ground. Xiao Ming wants to know the color of the balloon visible from each position. If there is no balloon above a position, output $0$.

Input Format

The first line contains three integers $n, m, k$, indicating the size of the grassland is $n$ rows and $m$ columns, and there are $k$ balloons in the sky.

The next $k$ lines each contain four integers: $x_i, y_i, h_i, c_i$, indicating the $i$-th balloon is located above the $x_i$-th row and $y_i$-th column, at a height $h_i$ from the ground, and its color is $c_i$.

Output Format

The output consists of $n$ lines, each containing $m$ numbers. The $i$-th line and $j$-th number represent the color of the balloon visible from that position. If there is no balloon above that position, output $0$.

Sample Input and Output

Input Sample #1

2 2 5
2 1 4 4
1 2 8 9
1 2 9 4
1 1 8 3
2 1 9 3

Output Sample #1

3 9
4 0

Input Sample #2

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

Output Sample #2

7 0 0
4 1 0
3 0 0

Notes

Sample 1 Explanation

• Above the first row and first column, there is only one balloon, color $3$;
• Above the first row and second column, the balloon closest to the ground is at height $8$, color $9$;
• Above the second row and first column, the balloon closest to the ground is at height $4$, color $4$;
• Above the second row and second column, there is no balloon.

Data Size and Constraints

For $100\%$ of the data, $1 \leq n, m \leq 10^3$, $1 \leq k \leq 10^5$, $1 \leq h_i, c_i \leq 10^9$. It is guaranteed that no two balloons have the exact same position ($x_i, y_i, h_i$).

见题面 Input 部分

见题面 Output 部分