Skittlez. 品尝彩虹，解决彩虹。

Rainbow McRainbows 先生是 Skittlez 工厂彩虹包装部门的月度最佳员工（因为该部门只有他一个人工作）。

对于那些不熟悉的人，一袋 Skittlez 里面装满了小巧、圆润、色彩缤纷且带有水果味的水果糖。如果你曾经好奇它们是如何包装的，以及为什么袋子里总是不够多的绿色糖果，那么今天你很幸运，因为 McRainbows 先生将为你独家揭秘 Skittlez 袋子是如何装满的。

彩虹包装部门有两个组件：袋子网格和填充机。袋子网格被划分为 $N$ 行（编号从 $1$ 到 $N$）和 $N$ 列（编号从 $1$ 到 $N$），每个单元格包含一个需要填充各种颜色糖果的袋子。填充机用于将糖果倒入网格中的袋子，并接收以下类型的指令：$(x_1, y_1, x_2, y_2, c, k)$，这意味着对于满足 $x_1 \le i \le x_2$ 且 $y_1 \le j \le y_2$ 的每个单元格 $(i, j)$ 中的袋子，机器将倒入 $k$ 颗颜色为 $c$ 的糖果。

McRainbows 先生的工作相当枯燥，他唯一的职责就是操作填充机。每天开始时，网格中的所有袋子都是空的，主管会给他一份他必须输入机器的指令列表。因此，他决定编写一个程序来替他完成工作，这样他就可以专注于更具智力挑战性的活动，比如玩纸牌游戏。

不幸的是，当主管们看到他的高分增长得如此之快时，他们开始产生怀疑（和任何体面的公司一样，Skittlez 有一个内部纸牌游戏记分牌）。因此，他们要求他在每天结束时提交一份报告，说明哪些包装好的袋子包含一种“压倒性”的颜色。如果一个袋子中某种颜色的糖果数量严格大于该袋子中所有其他颜色糖果数量的总和，则称该颜色对于该袋子是压倒性的。

因为他不太清楚如何做到这一点，而且他不想浪费几天时间去研究，他请求你编写一个程序来计算这份报告。形式化地，给定袋子网格的大小 $N$ 和机器在一天内接收到的指令列表，你想要输出一个与网格行数和列数相同的矩阵 $B$，其中：

$$B_{i,j} = \begin{cases} c, & \text{如果单元格 } (i, j) \text{ 中袋子的压倒性颜色为 } c, \\ -1, & \text{否则。} \end{cases}$$

输入格式

输入的第一行包含两个正整数 $N$，即袋子网格的大小，以及 $Q$，即当天机器接收到的指令数量。

接下来的 $Q$ 行，每行包含六个正整数 $x_1, y_1, x_2, y_2, c$ 和 $k$，描述一条指令。输入行中的值由空格分隔。

输出格式

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

数据范围

• $1 \le N \le 1\,000$
• $1 \le Q \le 500\,000$
• $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$

样例

样例输入 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 1 3
-1 -1 3 3 3

样例输入 2

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

样例输出 2

-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

说明

注意！样例输出中的额外空格是为了方便查看；你只需要在任意两个连续的值之间打印一个空格。