Problem 3327: Skittlez

Skittlez. Taste the rainbow, solve the rainbow.

Mr. Rainbow McRainbows is the employee of the month in the Skittlez factory's Department of Rainbow Packing (as he is the only one working in this department).

For those unfamiliar with them, a bag of Skittlez is filled with small, round, colorful pieces of candy that taste like fruits. If you ever wondered how they are packed and why there are never enough green ones in a bag, today is your lucky day, as Mr.~McRainbows will give you an exclusive into how the Skittlez bags are filled.

Task

The Rainbow Packing Department has two components: the bags grid and the filling machine. The bags grid is divided into $N$ rows (numbered from $1$ to $N$ ) and $N$ columns (numbered from $1$ to $N$ ), where each cell contains a bag that has to be filled with candy of various colors. The filling machine is used to pour candy into the bags from the grid and takes commands of the following type: $(x_1, y_1, x_2, y_2, c, k)$ , meaning that in each bag from a cell $(i, j)$ with $x_1 \leq i \leq x_2$ and $y_1 \leq j \leq y_2$ , the machine will pour $k$ candy pieces of color $c$ .

Mr. McRainbows has a fairly boring job, with his only responsibility being to operate the filling machine. At the beginning of each day, all the bags in the grid are empty, and Rainbow's supervisors give him a list of commands that he has to enter into the machine. Hence, he decided to write a program that does his job for him so he can focus on more intellectual activities like playing Solitaire.

Unfortunately, his supervisors started getting suspicious when they saw how much his high score increased (as with any respectable company, Skittlez has an internal Solitaire scoreboard). Consequently, they asked him to file a report at the end of each day stating which of the packed bags contain an overwhelming color. A color is considered overwhelming for a bag if there are strictly more candy pieces of that color in the bag than all others in the bag combined.

Because he doesn't really know how to do that, and he doesn't want to waste a few days figuring it out, he asks you to write a program that will compute the report. Formally, you are given the size of the bags grid $N$ and the list of commands the machine receives in a day, and you want to output a matrix $B$ with the same number of rows and columns as the grid where:

B_{i, j} = \begin{cases} c, & \text{if the overwhelming color in the bag in cell $(i, j)$ is $c$,} \\ -1, & \text{otherwise.} \end{cases}

Input data

The first line of the input contains two positive integer numbers $N$ , the size of the bags grid, and $Q$ , the number of commands the machine receives on the given day.

Each of the next $Q$ lines contains six positive integers, $x_1$ , $y_1$ , $x_2$ , $y_2$ , $c$ and $k$ , describing a command. The values on each input line are separated by spaces.

Output data

Output $N$ lines, each containing $N$ space-separated integers, representing the matrix $B$ described above.

Restrictions and clarifications

$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$
Note! The extra spaces in the examples' output have been added for better visibility; you should print only one space between any two consecutive values.

#	Points	Restrictions
1	7	$N, Q \leq 20$ and $k \leq 5$
2	21	There are at most $20$ different candy colours.
3	44	$N \leq 300$ and $Q \leq 100 \ 000$
4	28	No further restrictions.

Example 1

stdin

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

stdout

 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

Example 2