Description

On an $n \times n$ grid, there are $m$ carpets. Given the information of these carpets, determine how many carpets cover each cell.

Input Format

The first line contains two positive integers $n, m$, as described above. Then follow $m$ lines. Each line gives two coordinates $(x_1,y_1)$ and $(x_2,y_2)$, representing a carpet whose top-left corner is $(x_1,y_1)$ and bottom-right corner is $(x_2,y_2)$.

Output Format

Output $n$ lines, each containing $n$ non-negative integers. The integer in row $i$ and column $j$ denotes how many carpets cover the cell $(i,j)$.

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

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

Hint

Sample Explanation

After covering the first carpet:

After covering the first and second carpets:

After covering all carpets:

Constraints

For $20\%$ of the testdata, $n \le 50$, $m \le 100$. For $100\%$ of the testdata, $n, m \le 1000$.

Translated by ChatGPT 5