Oximoron

"Iași e mega tuff" - LucaLucaM, ianuarie 2025.

Cerință

Se dă o matrice $A$ cu $N$ linii și $M$ coloane, formată din valori distincte de la 1 la $N \cdot M$. Considerăm o matrice $B$, tot de $N$ linii și $M$ coloane, inițial având toate elementele egale cu $0$. Se dau $Q$ operații de forma: $div, x_1, y_1, x_2, y_2$.
Pentru fiecare astfel de operație, se va adăuga $1$ în matricea $B$ la toate valorile de pe pozițiile aflate pe linia $i$ cu $x_1 \le i \le x_2$ și coloana $j$ cu $y_1 \le j \le y_2$ pentru care valoarea $A_{i,j}$ (adică valoarea aflată pe linia $i$ și coloana $j$ în $A$) este divizibilă cu $div$. Cu alte cuvinte, pentru fiecare operație se va adăuga $1$ în matricea $B$ la toate pozițiile conținute în dreptunghiul cu colțul stânga sus $x_1, y_1$ și colțul dreapta jos $x_2, y_2$ care conțin în matricea $A$ o valoare divizibilă cu $div$. De asemenea, valorile $div$ sunt distincte, adică nu există două operații diferite care să aibă valoare $div$.

Date de intrare

Pe prima linie a fișierului de intrare oximoron.in se găsesc două numere întregi, $N$ și $M$.
Pe următoarele $N$ linii se vor găsi câte $M$ numere naturale, reprezentând elementele matricii.
Pe următoarea linie se va găsi un numar natural $Q$.
Pe următoarele $Q$ linii, se vor găsi câte 5 numere naturale $div$, $x_1$, $y_1$, $x_2$, $y_2$, ce descriu operațiile explicate mai sus.

Date de ieșire

În fișierul de ieșire oximoron.out se vor găsi $N$ linii a câte $M$ numere naturale, reprezentând matricea $B$ formată în urma aplicării operațiilor.

Restricții și precizări

• $1 \leq N \cdot M \leq 200 \ 000$;
• $1 \leq Q \leq N \cdot M$
• $1 \leq x_1, x_2 \leq N$
• $1 \leq y_1, y_2 \leq M$
• $1 \leq div \leq N \cdot M$
• Nu va apărea aceeași valoare $div$ în descrierea a oricăror două operații diferite.

Exemplul

oximoron.in

4 5
17 3 5 4 2
15 19 18 1 11
9 6 13 8 10
20 16 12 14 7
3
5 1 1 3 3
3 1 3 4 3
2 2 2 4 4

oximoron.out

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

Explicație

Pentru prima operație, elementele incluse în submatricea cu colțul stânga sus în $1, 1$ și dreapta jos în $3, 3$ și care sunt divizibile cu $5$ sunt 5, 15.
Pentru a doua operație, elementele incluse în submatricea cu colțul stânga sus în $1, 3$ și dreapta jos în $4, 3$ și care sunt divizibile cu $3$ sunt 18, 12.
Pentru a treia operație, elementele incluse în submatricea cu colțul stânga sus în $2, 2$ și dreapta jos în $4, 4$ și care sunt divizibile cu $2$ sunt 18, 6, 8, 16, 12, 14.
Astfel, adunăm $1$ la pozițiile unde se afla în matricea $A$ elemntele 5, 15, 6, 8, 16, 14 și $2$ la pozițiile unde se află în matricea $A$ elementele 18, 12.