题目描述

现在有一块很大的草原，这个草原分成了 $n$ 行 $m$ 列。 在这块草原的天空中，飘着 $k$ 个气球。第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。

从一个位置向上看，只能看到这个位置正上方的，距离地面最近的气球。小明想知道，从每个位置向上看，能看到的气球的颜色分别是什么。如果这个位置上空没有气球，则输出 $0$。

输入格式

第一行，包括三个整数 $n,m,k$，表示草原大小为 $n$ 行 $m$ 列，天空中有 $k$ 个气球。

接下来的 $k$ 行，每行包括四个整数：$x_i,y_i,h_i,c_i$，表示第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。

输出格式

共包含 $n$ 行，每行 $m$ 个数字。其中第 $i$ 行第 $j$ 个数字表示从这个位置向上看能看到的气球的颜色。如果这个位置上空没有气球，则输出 $0$。

测试样例

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

3 9
4 0

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

7 0 0
4 1 0
3 0 0

说明/提示

样例 1 解释

• 第一行第一列上空只有一个气球，颜色为 $3$；
• 第一行第二列上空高度最低的气球高度为 $8$，颜色为 $9$；
• 第二行第一列上空高度最低的气球高度为 $4$，颜色为 $4$；
• 第二行第二列上空没有气球。

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n, m \leq 10^3$，$1 \leq k \leq 10^5$，$1 \leq h_i, c_i \leq 10^9$。保证不存在两个气球的位置（$x_i, y_i, h_i$）完全相同。