Cerința

Specialiștii de la WHO (World Health Organization) trebuie să realizeze o statistică a numărului de cazuri de COVID 19 în anumite zone ale planetei. Aceștia își delimitează zonele respective și fiecare zonă o codifică printr-un element într-o matrice pătratică de dimensiune N, a cărui valoare reprezintă câte cazuri există în acea zonă. Inițial, se cunoaște câte cazuri există în fiecare zonă înainte de realizarea statisticii. Asupra matricei inițiale alcătuită din aceste valori se aplică 2 tipuri de operații:

• 1 x y val – în zona codificată în matrice prin elementul de coordonate x y apar val cazuri noi, deci elementul de coordonate x y din matrice crește cu val.
• 2 x1 y1 x2 y2 – se cere numărul total de cazuri din toate zonele codificate printr-un element aflat în submatricea cu colțul stânga-sus de coordonate x1 y1 și cel drepta-jos de coordonate x2 y2 (adică suma elementelor submatricei cu colțul stânga-sus de coordonate x1 y1 și cel drepta-jos de coordonate x2 y2).

Dându-se Q operații, să se raspundă în ordine la cele de tip 2.

Date de intrare

Fișierul de intrare aib2d.in conține pe prima linie numărul N, iar pe următoarele N linii câte N numere naturale separate prin câte un spațiu reprezentând elementele matricei. Pe linia N + 2 se află numărul Q reprezentând numărul de operații, iar pe următoarele Q linii sunt descrise operațiile.

Date de ieșire

Fișierul de ieșire aib2d.out va conține pe câte o linie răspunsurile la operațiile de tip 2 în ordinea în care apar în fișierul de intrare.

Restricții și precizări

• 1 ≤ N ≤ 1.000
• 1 ≤ Q ≤ 100.000
• 1 ≤ x, y, x1, y1, x2, y2 ≤ N
• x1 ≤ x2
• y1 ≤ y2
• 1 ≤ val ≤ 2.500
• elementele matricei inițiale vor fi mai mici sau egale decât 2.500
• orice sumă care va trebui calculată va putea fi reprezentată pe 32 de biți
• datorită dimensiunilor mari ale fișierelor se recomandă parsarea acestora
• InParser
• OutParser

Exemplu:

aib2d.in

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

aib2d.out

64
80

Explicație

Dupa prima operatie elementul de pe linia 1 și coloana 3 va avea valoarea 9, iar rezultatul operatiei de tip 2 imediat următoare va fi 64 (inițial ar fi fost 60 dar elementul de pe linia 1 și coloana 3 a crescut cu 4).