P3397 Carpets

[Enhanced Version](/problem/P13787)

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

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 $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)$.

### Sample Explanation After covering the first carpet: |$0$|$0$|$0$|$0$|$0$| |:-:|:-:|:-:|:-:|:-:| |$0$|$1$|$1$|$0$|$0$| |$0$|$1$|$1$|$0$|$0$| |$0$|$0$|$0$|$0$|$0$| |$0$|$0$|$0$|$0$|$0$| After covering the first and second carpets: |$0$|$0$|$0$|$0$|$0$| |:-:|:-:|:-:|:-:|:-:| |$0$|$1$|$1$|$0$|$0$| |$0$|$1$|$2$|$1$|$1$| |$0$|$0$|$1$|$1$|$1$| |$0$|$0$|$1$|$1$|$1$| After covering all carpets: |$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$| --- ### 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