Skittlez (RMI contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: segment tree, divide and conquer

Romanian Master of Informatics, Day 1
Bucharest, Romania
Thursday 28th November, 2024

# Problem Skittlez

| Input file  | `stdin`  |
|-------------|----------|
| Output file | `stdout` |

*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.

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 \le i \le x_2$ and $y_1 \le j \le 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) \text{ 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.

![](_page_1_Picture_1.jpeg)

## Output data

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

### Restrictions

- $1 \le N \le 1000$
- $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$

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

### Examples

| Input file   | Output file              |
|--------------|--------------------------|
| `5 3`        | `1 1 -1 -1 -1`           |
| `1 3 5 5 3 3`  | `1 1 1 1 -1`             |
| `2 2 4 4 1 5`  | `1 1 1 1 -1`             |
| `1 1 3 5 1 3`  | `-1 1 1 1 3`             |
|              | `-1 -1 3 3 3`            |
| `10 10`       | `-1 1 1 1 1 2 2 2 2 2`    |
| `1 6 6 10 2 4` | `-1 1 1 1 2 2 2 2 2 2`    |
| `5 4 9 8 2 5`  | `-1 -1 -1 -1 2 2 2 2 2 2` |
| `2 7 6 9 2 3`  | `-1 -1 -1 -1 -1 2 2 2 2 2`|
| `6 3 10 9 6 4` | `1 1 1 2 2 2 2 2 2 2`     |
| `1 2 2 10 1 3` | `1 1 6 -1 -1 2 2 2 2 2`   |
| `5 1 7 6 1 3`  | `1 1 6 -1 -1 2 2 2 6 -1`  |
| `9 1 9 2 2 4`  | `-1 -1 6 2 2 2 2 2 6 -1`  |
| `4 6 8 7 2 3`  | `2 2 6 2 2 2 2 2 6 -1`    |
| `2 5 3 7 2 4`  | `-1 -1 6 6 6 6 6 6 6 -1`  |
| `1 8 6 10 2 3` |                          |

**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.

Starter code:

Grader code:

Setup script:

Evaluation script: