polen

În Grădina Botanică Regală „Etherea", cercetătorii studiază o specie rară de cireș japonez, numită Sakura Tennyo. Grădina este reprezentată printr-o matrice cu $N$ linii și $M$ coloane, în care fiecare celulă corespunde unei parcele de pământ. Inițial, toate parcelele au fertilitatea $0$.

În grădină au loc, pe rând, $Q$ înfloriri. O înflorire din celula $(r, c)$, având puterea $K$, eliberează polen care, purtat de curenții de aer, se poate răspândi în cel mult 4 zone triunghiulare. Existența acestor curenți este indicată de o cheieeoliană formată din 4 semnale, numerotate $0$, $1$, $2$ și $3$.

Pentru o înflorire, curentul apare doar dacă semnalul corespunzător este activ.

Valoarea cheie codifică semnalele active ca o mască de biți. Semnalul $b$ este activ dacă și numai dacă bitul $b$ din cheie este $1$, pentru $b \in \{0, 1, 2, 3\}$. De exemplu, cheia $5$ are reprezentarea binară $0101_2$, deci sunt active semnalele $0$ și $2$. Curenții corespunzători celor 4 semnale sunt definiți astfel:

Fiecare celulă atinsă de polenul unui cireș își crește fertilitatea cu $val$. Unii cireși produc polen inhibitor, astfel $val$ poate fi negativ, iar fertilitatea unei celule poate scădea. Contribuțiile (pozitive și negative) se adună. Dacă doi curenți ai aceluiași cireș ating aceeași celulă, contribuțiile se adună; de exemplu, dacă doi curenți trec prin $(r, c)$, atunci acolo se adaugă $2 \cdot val$.

Se iau în considerare doar celulele aflate în interiorul matricei. Orice porțiune a unei zone de înflorire care depășește marginile matricei va fi ignorată.

Cerințe

Se cere determinarea matricei finale a fertilității după aplicarea tuturor celor $Q$ înfloriri, pentru una dintre următoarele trei variante:

Cerința 1

Pentru această cerință, înfloririle se vor aplica uniform pe zone care formează pătrate în matrice. Astfel, se garantează că $Q$ este par, iar înfloririle sunt grupate în perechi aflate pe poziții consecutive (în funcție de numărul lor de ordine): înflorirea $1$ cu $2$, $3$ cu $4$, $\ldots$, $Q - 1$ cu $Q$.

Pentru fiecare pereche, prima înflorire are activ exact un singur semnal, iar a doua are activ exact semnalul opus acestuia, semnalele opuse considerându-se $0$ cu $1$, respectiv $2$ cu $3$. De asemenea, ambele înfloriri din pereche au aceeași valoare $val$.

Mai mult, dacă prima înflorire din pereche are coordonatele $(r, c)$ și puterea $K$, atunci a doua înflorire are puterea $K - 1$, iar semnalul activ și coordonatele ei se determină conform tabelului următor:

Cerința 2

Pentru fiecare înflorire sunt active simultan toate cele 4 semnale.

Cerința 3

Pentru fiecare înflorire poate fi activă orice submulțime a celor 4 semnale.

Date de intrare

Fișierul polen.in conține:

• pe prima linie, un număr natural $C$, reprezentând cerința care trebuie rezolvată;
• pe a doua linie, trei numere naturale $N$, $M$, $Q$, cu semnificația din enunț;
• pe următoarele $Q$ linii, câte cinci numere întregi $r$, $c$, $K$, $val$, $cheie$, cu semnificația din enunț.

Date de ieșire

Fișierul polen.out va conține $N$ linii, fiecare având câte $M$ numere întregi separate prin spațiu, reprezentând fertilitatea finală a fiecărei parcele din grădină.

Restricții și precizări

• $C \in \{1, 2, 3\}$
• $1 \leq N, M, K \leq 1 \ 000$
• $1 \leq Q \leq 1 \ 000 \ 000$
• $1 \leq r \leq N$
• $1 \leq c \leq M$
• $0 \leq cheie \leq 15$
• $-10^9 \leq val \leq 10^9$
• Se garantează pentru primele 9 subtaskuri că toate zonele de înflorire se află în interiorul matricei.

Exemplul 1

polen.in

1
10 11 6
4 2 2 1 1
2 4 1 1 2
5 4 2 1 1
3 6 1 1 2
9 7 3 1 1
6 10 2 1 2

polen.out

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

Explicație

În matricea alăturată, culorile indică zona acoperită de fiecare pereche de înfloriri:

• Albastru - înfloririle 1 și 2
• Portocaliu - înfloririle 3 și 4
• Verde - înfloririle 5 și 6
• Mov - intersecția zonei albastre cu cea portocalie

Exemplul 2

polen.in

2
9 9 1
5 5 4 1 15

polen.out

0 0 0 0 2 0 0 0 0
0 0 0 1 2 1 0 0 0
0 0 1 1 2 1 1 0 0
0 1 1 1 2 1 1 1 0
2 2 2 2 4 2 2 2 2
0 1 1 1 2 1 1 1 0
0 0 1 1 2 1 1 0 0
0 0 0 1 2 1 0 0 0
0 0 0 0 2 0 0 0 0

Explicație

În matricea alăturată:

• valorile albastre sunt celule acoperite o singură dată;
• valorile mov sunt celule acoperite de două triunghiuri;
• valoarea roșie din centru este acoperită de toate cele 4 triunghiuri.

Exemplul 3

polen.in

3
10 10 4
2 2 2 1 1
3 7 2 1 3
8 3 2 1 11
7 8 2 1 15

polen.out

0 1 1 0 0 0 1 0 0 0
0 1 1 1 0 0 1 1 0 0
0 0 0 0 1 1 2 1 1 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 1 2 0 0
0 0 1 0 0 0 1 2 1 0
0 0 1 1 0 2 2 4 2 2
1 1 3 2 2 0 1 2 1 0
0 1 2 1 0 0 0 2 0 0
0 0 2 0 0 0 0 0 0 0

Explicație

În matricea alăturată, fiecare culoare indică contribuția unei înfloriri:

• Albastru - Prima înflorire, cu un singur semnal activ;
• Portocaliu - A doua înflorire, cu două semnale active;
• Verde - A treia înflorire, cu trei semnale active;
• Roșu - A patra înflorire, cu toate cele 4 semnale active.