시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)74241934.545%

문제

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

서브태스크 1 (1점)

Modified constraints apply: $1 \le N \le 300;$ $1 \le Q \le 1\,000;$ also, $s_\mathbf{F}=e_\mathbf{F}=N$ for all queries.

서브태스크 2 (3점)

Modified constraints apply: $1 \le N \le 300;$ $1 \le Q \le 1\,000$.

서브태스크 3 (25점)

Modified constraints apply: $1 \le N \le 1\,000;$ $1 \le Q \le 10\,000$.

서브태스크 4 (71점)

Original constraints apply: $1 \le N \le 1\,000;$ $1 \le Q \le 200\,000$.

예제 입력 1

5
110 120 130 140 150
210 220 230 240 250
310 320 330 340 350
410 420 430 440 450
510 520 530 540 550
2
5 6 3 7 15
2 3 4 5 24

예제 출력 1

110 144 130 140 150
210 244 230 255 250
310 320 345 355 350
410 435 445 440 450
510 520 530 540 550

This test corresponds to the Subtask 2.

노트

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.