A Minecraft House#12216

A Minecraft House

4 seconds

1,024 megabytes

Very hard

Hazoq just got out of the cave and now he wants to build his house. After he found the perfect piece of land, which can be described as a $2$ D array $a$ consisting of $n$ rows and $m$ columns with rows numbered from $1$ to $n$ (top to bottom) and columns numbered from $1$ to $m$ (left to right) filled with integers, he decided to follow one of WiederDude's tutorials. But the tutorial was so long and boring, so he's counting on you to summarize the tutorial for him.

The tutorial consists of $q$ steps. On the $k$ -th step you are given five integers $x$ , $y$ , $d$ , $c$ , $s$ and you need to place $s$ blocks on top of every cell $(i, j)$ such that:

$(x - i)^{2} + (y - j)^{2} \leq d$ \sqrt{(x-i)^2+(y-j)^2} \le d.
$a_{i, j}$ a_{i, j} is a multiple of $c$ .

You have to output a $2$ D array $b$ consisting of $n$ rows and $m$ columns, with $b_{i, j}$ b_{i, j} being the number of blocks placed on top of the cell $(i, j)$ after performing all the $q$ steps.

Notice that the array $a$ is different from the array $b$ and it doesn't get affected by the queries.

Input

The first line consists of two integers $n$ , $m$ ( $1 \leq n \cdot m \leq 1 0^{5}$ 1 \le n \cdot m \le 10^5) — the dimensions of the grid.

The following $n$ lines are the description of the array $a$ , with the $i$ -th line containing $m$ integers $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ a_{i, 1}, a_{i, 2}, \ldots, a_{i, m} ( $0 \leq a_{i, j} \leq 1 0^{6}$ 0 \le a_{i, j} \le 10^6).

The next line consists of a single integer $q$ ( $1 \leq q \leq 1 0^{5}$ 1 \le q \le 10^5) — the number of steps.

The next $q$ lines each contain five integers $x$ , $y$ , $d$ , $c$ , $s$ ( $1 \leq x \leq n$ 1 \le x \le n, $1 \leq y \leq m$ 1 \le y \le m, $0 \leq d \leq 1 0^{5}$ 0 \le d \le 10^5, $1 \leq c \leq 1 0^{6}$ 1 \le c \le 10^6, $1 \leq s \leq 1 0^{10}$ 1 \le s \le 10^{10}).

Output

The output consists of $n$ lines.

The $i$ -th line contains $m$ integers $b_{i, 1}, b_{i, 2}, \dots, b_{i, m}$ b_{i, 1}, b_{i, 2}, \ldots, b_{i, m}.

Examples

Example 1

Loading

Scoring

Subtask $1$ ( $20$ points): $n \cdot m \leq 1 0^{3}$ n \cdot m \le 10^3
Subtask $2$ ( $20$ points): $n = 1$ n = 1
Subtask $3$ ( $30$ points): $c = 1$ c = 1
Subtask $4$ ( $40$ points): $x = 1$ x = 1, $y = 1$ y = 1
Subtask $5$ ( $40$ points): $n \cdot m \leq 1 0^{4}$ n \cdot m \le 10^4
Subtask $6$ ( $50$ points): $a_{i}, c \leq 1000$ a_i, c \le 1000
Subtask $7$ ( $50$ points): $a_{i}, c \leq 1 0^{5}$ a_i, c \le 10^5
Subtask $8$ ( $50$ points): $c \leq 100$ c \le 100
Subtask $9$ ( $200$ points): No additional constraints.

(x - i)^{2} + (y - j)^{2} \leq d

a_{i, j}

b_{i, j}

1 \leq n \cdot m \leq 1 0^{5}

a_{i, 1}, a_{i, 2}, \dots, a_{i, m}

0 \leq a_{i, j} \leq 1 0^{6}

1 \leq q \leq 1 0^{5}

1 \leq x \leq n

1 \leq y \leq m

0 \leq d \leq 1 0^{5}

1 \leq c \leq 1 0^{6}

1 \leq s \leq 1 0^{10}

b_{i, 1}, b_{i, 2}, \dots, b_{i, m}

n \cdot m \leq 1 0^{3}

n = 1

c = 1

x = 1

y = 1

n \cdot m \leq 1 0^{4}

a_{i}, c \leq 1000

a_{i}, c \leq 1 0^{5}

c \leq 100