Line-Based Matrix Addition

You are given an $N \times N$ matrix $A$.

Two types of lines exist on the matrix: rising and falling. There are $2N-1$ lines for each type, where rising lines are numbered $\mathrm{RL}_i$ and falling lines are numbered $\mathrm{FL}_i$ for each $1 \le i \le 2N-1$. The below picture illustrates the line layout when $N=5$.

You have to perform $Q$ cumulative queries in order on this matrix, which is given by the input as:

• $s_\mathrm{R}$ $e_\mathrm{R}$ $s_\mathrm{F}$ $e_\mathrm{F}$ $v$.

Each query specifies two line ranges of different types on the matrix, which is $\left\{ \mathrm{RL}_i \mid s_\mathrm{R} \le i \le e_\mathrm{R} \right\}$ and $\left\{ \mathrm{FL}_i \mid s_\mathrm{F} \le i \le e_\mathrm{F} \right\}$, and a value $v$. You should add the value $v$ to every element in the intersection of such range, i.e., $$\left\{ \mathrm{RL}_i \mid s_\mathrm{R} \le i \le e_\mathrm{R} \right\} \quad \cap \quad \left\{ \mathrm{FL}_i \mid s_\mathrm{F} \le i \le e_\mathrm{F} \right\}.$$

The following example illustrates the elements to update when $N=5$, $[s_\mathrm{R},e_\mathrm{R}]=[5,6]$, and $[s_\mathrm{F},e_\mathrm{F}]=[3,7]$:

Write a program to perform the queries and output the final status of the matrix $A$.

The first line of input contains a single integer, $N$, denoting the matrix size. ($1 \le N \le 1\,000$)

The next $N$ lines of input contain $N^2$ integers, where each line has $N$ space-separated integers, denoting the value of the matrix. Here, the $j$-th integer of the $i$-th line denotes $A_{ij}$. ($-10^9 \le A_{ij} \le 10^9$)

The next line contains a single integer, $Q$, denoting the query count. ($1 \le Q \le 200\,000$)

The $i$-th of the next $Q$ lines of input contain five space-separated integers: $s_\mathrm{R}$, $e_\mathrm{R}$, $s_\mathrm{F}$, $e_\mathrm{F}$, and $v$, denoting the $i$-th query explained earlier. ($1 \le s_\mathrm{R} \le e_\mathrm{R} \le 2N-1;$ $1 \le s_\mathrm{F} \le e_\mathrm{F} \le 2N-1;$ $-10^9 \le v \le 10^9$)

Output $N$ lines denoting the updated value of the matrix $A$. Each line should contain $N$ space-separated integers. The $j$-th integer of the $i$-th line should represent $A_{ij}$.

(For Sogang students:) Note that this problem is an improvised version that matches the format of a problem in a general programming contest. While in the exam, the original scoring was:

• $40$ points for Subtask 1.
• $30$ points for Subtask 2.
• $25$ points for Subtask 3.
• $5$ points for Subtask 4.