Carpet Coverage

Given an \(n \times n\) grid and \(m\) carpets. Each carpet covers a subrectangle of the grid. The i-th carpet is described by four integers \(x_1\), \(y_1\), \(x_2\), and \(y_2\), representing the top-left and bottom-right corners (1-indexed) of the carpet. Determine, for every cell in the grid, the number of carpets covering that cell.

inputFormat

The first line contains two integers \(n\) and \(m\). Each of the next \(m\) lines contains four integers \(x_1, y_1, x_2, y_2\) describing a carpet.

outputFormat

Print \(n\) lines, each containing \(n\) space-separated integers. The \(j\)-th integer in the \(i\)-th line indicates the number of carpets covering the cell at row \(i\) and column \(j\).

sample

4 2
1 1 2 2
2 2 4 4

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