Î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 cheie eoliană 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 ∈ {0, 1, 2, 3}. De exemplu, cheia 5 are reprezentarea binară 01012, deci sunt active semnalele 0 și 2. Curenții corespunzători celor 4 semnale sunt definiți
astfel:

Tabela 1: Distribuția polenului în funcție de semnal

Fiecare celulă atinsă de polenul unui cireș își crește fertilitatea cu 𝑣𝑎𝑙. Unii cireși produc polen inhibitor, astfel 𝑣𝑎𝑙 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 · 𝑣𝑎𝑙.

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, . . . , 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 de intrare polen.in conține:

• pe prima linie, un număr natural C, reprezentând cerint,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 de ieșire 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 ∈ {1, 2, 3}
• 1 ≤ N,M,K ≤ 1 000
• 1 ≤ Q ≤ 1 000 000
• 1 ≤ r ≤ N
• 1 ≤ r ≤ M
• 0 ≤ cheie ≤ 15
• −109 ≤ 𝑣𝑎𝑙 ≤ 109
• Se garantează pentru primele 9 subtaskuri că toate zonele de înflorire se află în interiorul matricei.
• Datorită dimensiunilor mari, nu au fost adăugate toate testele folosite în concurs.

Subtaskuri

• C = 1, N,M,Q ≤ 200
• C = 1, Q ≤ 5 000
• C = 1. Fără alte resticții suplimentare.
• C = 2, N,M,Q ≤ 200
• C = 2, Q ≤ 5 000
• C = 2. Fără alte resticții suplimentare.
• C = 3, N,M,Q ≤ 200
• C = 3, Q ≤ 5 000
• C = 3. Fără alte resticții suplimentare.
• C = 3. Zonele de înflorire pot depăși marginile matricei. Fără alte resticții suplimentare.

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

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