题目描述

题目译自 Romanian Master of Informatics 2024 Day1 T3 「Skittlez」

Skittlez. Taste the rainbow, solve the rainbow.

在彩虹糖工厂的彩虹包装部，彩虹·麦克雷恩博斯先生荣膺本月最佳员工（毕竟他是这个部门唯一的工作人员）。

如果你还不了解彩虹糖，它是一种装满小小的、圆圆的、五颜六色糖果的小袋子，每颗糖果都带着水果的香甜滋味。你有没有好奇过这些糖果是如何装袋的？为什么绿色的糖果总是那么少？今天是你的幸运日！麦克雷恩博斯先生将为你独家揭秘彩虹糖袋的填充过程。

彩虹包装部有两个核心部分：糖袋网格和填充机。糖袋网格被划分为 $N$ 行（从 $1$ 到 $N$ 编号）和 $N$ 列（同样从 $1$ 到 $N$ 编号），每个单元格里放着一个待填充的糖袋，里面会装入各种颜色的糖果。填充机负责将糖果倒进网格中的糖袋，它接受的指令格式是这样的：$(x_1, y_1, x_2, y_2, c, k)$，意思是对于网格中坐标 $(i, j)$ 满足 $x_1 \leq i \leq x_2$ 且 $y_1 \leq j \leq y_2$ 的每个糖袋，填充机都会倒入 $k$ 颗颜色为 $c$ 的糖果。

麦克雷恩博斯的工作其实挺单调的，他唯一的职责就是操作填充机。每天早上，网格里所有的糖袋都是空的，他的上司会给他一份指令清单，让他输入到机器里。为了让自己解放出来去做更有意思的事（比如玩纸牌接龙），他决定写一个程序来自动完成这项工作。

然而，当上司们发现他的接龙高分在公司内部排行榜上突飞猛进时（毕竟彩虹糖公司可是个重视接龙排名的正经企业），他们起了疑心。于是，他们要求他每天提交一份报告，标明哪些糖袋里出现了压倒性颜色。所谓压倒性颜色，就是指某个糖袋中某种颜色的糖果数量严格超过该袋子里所有其他颜色糖果数量的总和。

麦克雷恩博斯不会写这个程序，也不想花几天时间去琢磨，所以他找到了你帮忙。你的任务是编写一个程序来生成这份报告。正式来说，你会拿到糖袋网格的大小 $N$ 和一天内填充机接收的指令清单，然后输出一个与网格行数列数相同的矩阵 $B$，其中：

$$B_{i, j} = \begin{cases} c, & \text{如果单元格 $(i, j)$ 的糖袋中压倒性颜色是 $c$，} \\ -1, & \text{其他情况} \end{cases} $$

输入格式

输入的第一行包含两个正整数 $N$ 和 $Q$，分别表示糖袋网格的大小和当天填充机接收的指令数量。

接下来的 $Q$ 行，每行包含六个正整数 $x_1, y_1, x_2, y_2, c, k$，描述一条指令。每行数据之间用空格分隔。

输出格式

输出 $N$ 行，每行包含 $N$ 个空格分隔的整数，表示上述矩阵 $B$。

注意！ 样例输出中为了清晰显示加了额外的空格，实际输出时每两个相邻值之间只需一个空格。

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

 1  1 -1 -1 -1
 1  1  1  1 -1
 1  1  1  1 -1
-1  1  1  1  3
-1 -1  3  3  3

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

-1  1  1  1  1  2  2  2  2  2
-1  1  1  1  2  2  2  2  2  2
-1 -1 -1 -1  2  2  2  2  2  2
-1 -1 -1 -1 -1  2  2  2  2  2
 1  1  1  2  2  2  2  2  2  2
 1  1  6 -1 -1  2  2  2  2  2
 1  1  6 -1 -1  2  2  2  6 -1
-1 -1  6  2  2  2  2  2  6 -1
 2  2  6  2  2  2  2  2  6 -1
-1 -1  6  6  6  6  6  6  6 -1

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 1 \ 000$
• $1 \leq Q \leq 500 \ 000$
• $1 \leq x_1 \leq x_2 \leq N$
• $1 \leq y_1 \leq y_2 \leq N$
• $1 \leq c \leq Q$
• $1 \leq k \leq 10^9$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$7$	$N, Q \leq 20$ 且 $k \leq 5$
$2$	$21$	糖果颜色种类不超过 $20$
$3$	$44$	$N \leq 300$ 且 $Q \leq 100 \ 000$
$4$	$28$	无额外限制