P11882 [RMI 2024] 彩虹糖 / Skittlez

$\text{\underline{Taste} the rainbow, \underline{solve} the rainbow.}$

彩虹糖包装机上有 $n$ 行 $n$ 列共 $n\times n$ 个袋子。我们记第 $i$ 行第 $j$ 列的袋子为 $(i,j)$。 有 $q$ 个操作：每个操作用六元组 $(x_1,y_1,x_2,y_2,c,k)$ 描述，意思是： - $\forall x_1\le i\le x_2$，$y_1\le j\le y_2$，在 $(i,j)$ 中放入 $k$ 颗颜色为 $c$ 的彩虹糖。 在所有操作完后，求出每一袋中，彩虹糖颜色的**绝对众数**。 定义一种颜色是绝对众数，当且仅当，它出现次数**严格大于**其他颜色出现次数之和。

第一行，两个正整数 $n,q$。 接下来 $q$ 行，每行六个正整数 $x_1,y_1,x_2,y_2,c,k$。

输出 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个数表示 $(i,j)$ 的绝对众数。 特别地，若绝对众数不存在，定义为 $-1$。

#### 样例解释 方便人类阅读的样例输出为 ```plain 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 ``` ```plain -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 ``` #### 数据范围 对于 $100\%$ 的数据，保证： - $1\le n\le 10^3$； - $1\le q\le 5\times 10^5$； - $1\le x_1\le x_2\le n$； - $1\le y_1\le y_2\le n$； - $1\le c\le q$； - $1\le k\le 10^9$。 --- - $\text{Subtask 0 (0 pts)}$：样例。 - $\text{Subtask 1 (7 pts)}$：$n,q\le 20$，$k\le 5$。 - $\text{Subtask 2 (21 pts)}$：至多有 $20$ 种颜色。 - $\text{Subtask 3 (44 pts)}$：$n\le 300$，$q\le 10^5$。 - $\text{Subtask 4 (28 pts)}$：无额外限制。