题目背景

$\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$。

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  1 -1 -1 -1
 1  1  1  1 -1
 1  1  1  1 -1
-1  1  1  1  3
-1 -1  3  3  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

数据范围

对于 $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)}$：无额外限制。