{"problem":{"name":"[语言月赛 202404] 天上的气球","description":{"content":"现在有一块很大的草原，这个草原分成了 $n$ 行 $m$ 列。 在这块草原的天空中，飘着 $k$ 个气球。第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。 从一个位置向上看，只能看到这个位置正上方的，距离地面最近的气球。小明想知道，从每个位置向上看，能看到的气球的颜色分别是什么。如果这个位置上空没有气球，则输出 $0$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3964"},"statements":[{"statement_type":"Markdown","content":"现在有一块很大的草原，这个草原分成了 $n$ 行 $m$ 列。\n在这块草原的天空中，飘着 $k$ 个气球。第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。\n\n从一个位置向上看，只能看到这个位置正上方的，距离地面最近的气球。小明想知道，从每个位置向上看，能看到的气球的颜色分别是什么。如果这个位置上空没有气球，则输出 $0$。\n\n## Input\n\n第一行，包括三个整数 $n,m,k$，表示草原大小为 $n$ 行 $m$ 列，天空中有 $k$ 个气球。\n\n接下来的 $k$ 行，每行包括四个整数：$x_i,y_i,h_i,c_i$，表示第 $i$ 个气球，位置在第 $x_i$ 行第 $y_i$ 列上空，距离地面高度 $h_i$，气球的颜色为 $c_i$。\n\n## Output\n\n共包含 $n$ 行，每行 $m$ 个数字。其中第 $i$ 行第 $j$ 个数字表示从这个位置向上看能看到的气球的颜色。如果这个位置上空没有气球，则输出 $0$。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n- 第一行第一列上空只有一个气球，颜色为 $3$；\n- 第一行第二列上空高度最低的气球高度为 $8$，颜色为 $9$；\n- 第二行第一列上空高度最低的气球高度为 $4$，颜色为 $4$；\n- 第二行第二列上空没有气球。\n\n### 数据规模与约定\n\n对于 $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$）完全相同。\n\n| 测试点编号 | $n, m$ | $k$ | $h_i$ | $c_i$ | 特殊性质 |\n| :-: | :-: | :-: | :-: | :-: | :-: |\n| $1$ | $= 2$ | $\\leq 10$ | $\\leq 10$ | $\\leq 10$ | 无 |\n| $2, 3$ | $ \\leq 10$ | $\\leq 200$ | $\\leq 10$ | $\\leq 10$ | 无 |\n| $4$ | $= 1$ | $\\leq 10^5$ | $\\leq 10^9$ | $\\leq 10^9$ | 无 |\n| $5$ | $\\leq 300$ | $\\leq 9 \\times 10^4$ | $\\leq 10^9$ | $\\leq 10^9$ | 每一个位置上空**恰好**有一个气球 | \n| $6$ | $\\leq 1000$ | $\\leq 10^5$ | $\\leq 10^9$ | $\\leq 10^9$ | 每一个位置上空**至多**有一个气球 | \n| $7$ | $\\leq 1000$ | $\\leq 10^5$ | $\\leq 10^9$ | $= 1$ | 无 | \n| $8 \\sim 10$ | $\\leq 1000$ | $\\leq 10^5$ | $\\leq 10^9$ | $\\leq 10^9$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3964","tags":["2024","O2优化","数组","语言月赛"],"sample_group":[["2 2 5\n2 1 4 4\n1 2 8 9\n1 2 9 4\n1 1 8 3\n2 1 9 3\n","3 9\n4 0\n"],["3 3 5\n1 1 6 7\n2 2 7 5\n3 1 8 3\n2 2 6 1\n2 1 3 4\n","7 0 0\n4 1 0\n3 0 0\n"]],"created_at":"2026-03-03 11:09:25"}}