Muuncreft

M-am ținut de cuvânt lil bro.

După ce a demonstrat că știe să construiască ferme automate (unele chiar funcționale), Buzdi a fost ales primar al orașului Muuncreft. Acesta poate fi reprezentat printr-o matrice $A$ cu $N$ linii și $N$ coloane, unde fiecare element al acesteia reprezintă valoarea importanței construcției aflate în acea poziție (fie ea o casă, o fermă, un spawner sau poate chiar nimic...).

În arhivele primăriei există o matrice specială infinită $P$, numită matricea productivității secrete. Buzdi are puține informații despre această matrice (e primar de-abia de o zi...). El știe doar că matricea $P$ arată în felul următor:

Buzdi a primit ordin de la superiori să trimită o statistică despre productivitatea orașului său, care să dovedească că respectă cerințele Uniunii Siediene. Fiind un mare pasionat de matematică, Buzdi decide să aleagă $Q$ submatrici din matricea $A$ și să le calculeze productivitatea creftiniană.

Productivitatea creftiniană a unei submatrici se calculează în felul următor:

• Submatricea se transformă într-o matrice independentă, numită $B$.
• Fiecare element al matricei $B$ se înmulțește cu valoarea din matricea $P$ de pe aceeași poziție.
• Valoarea productivității este egală cu suma elementelor din matricea $B$ nou obținută.

Cerință

Buzdi este ocupat cu birocrații de rutină (el este și secretar al orașului, atât a permis bugetul...) și vă roagă pe voi să îl ajutați cu două cerințe:

1. Să se afișeze primele $N$ linii și $N$ coloane ale matricei $P$.
2. Să se calculeze productivitatea creftiniană pentru fiecare din cele $Q$ submatrici alese de Buzdi.

Date de intrare

Pe prima linie a fișierului de intrare muuncreft.in se găsesc $3$ numere naturale, $C$, $N$ și $Q$, separate printr-un spațiu, reprezentând cerința ce trebuie rezolvată, dimensiunea matricei $A$ și numărul de submatrici alese de Buzdi. Pe următoarele $N$ linii se găsesc $N$ numere naturale, separate printr-un spațiu, reprezentând elementele matricei $A$. Pe următoarele $Q$ linii se găsesc $4$ numere naturale, $i_1 \ j_1 \ i_2 \ j_2$, separate printr-un spațiu, unde $(i_1, j_1)$ reprezintă colțul din stânga-sus al submatricei alese, iar $(i_2, j_2)$ reprezintă colțul din dreapta-jos al submatricei alese.

Date de ieșire

• Dacă $C = 1$, atunci pe următoarele $N$ linii ale fișierului de ieșire muuncreft.out se vor găsi $N$ numere naturale, separate printr-un spațiu, reprezentând elementele matricei $P$.
• Dacă $C = 2$, atunci pe următoarele $Q$ linii ale fișierului de ieșire muuncreft.out se va găsi un singur număr natural $v_i$, reprezentând productivitatea creftiniană a submatricei $i$ din cele $Q$ alese de Buzdi.

Restricții și precizări

• $1 \leq C \leq 2$;
• $1 \leq N \leq 2000$;
• $1 \leq Q \leq 200 \ 000$;
• $1 \leq A_{ij} \leq 10^6, 1 \leq i, j \leq N$;
• $1 \leq i_1 \leq i_2 \leq N$;
• $1 \leq j_1 \leq j_2 \leq N$;
• Liniile și coloanele sunt numerotate de la $1$;
• Poziția $(i, j)$ dintr-o matrice se referă la elementul aflat pe linia $i$ și coloana $j$;
• Submatricea delimitată de colțul stânga-sus $(i_1, j_1)$ și colțul dreapta-jos $(i_2, j_2)$ este formată din toate elementele $A_{ij}$ pentru care $i_1 \leq i \leq i_2$ și $j_1 \leq j \leq j_2$;
• Matricea $A$ nu se modifică în urma calculării productivității creftiniene;

  #	Punctaj	Restricții
  0	0	Exemplele
  1	19	$C = 1$
  2	15	$C = 2 \\ 1 \leq N \leq 100 \\ 1 \leq Q \leq 100$
  3	17	$C = 2$ și toate valorile din matricea $A$ sunt egale
  4	28	$C = 2 \\ 1 \leq N \leq 1000$
  5	21	$C = 2$

Exemplul 1

muuncreft.in

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

muuncreft.out

1 2 3 4 5 
2 4 6 8 10 
3 6 9 12 15 
4 8 12 16 20 
5 10 15 20 25 

Explicație

$C = 1$, deci se va rezolva doar cerința $1$. Se poate observa că matricea $P$ afișată coincide cu cea din enunț.

Exemplul 2

muuncreft.in

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

muuncreft.out

45
90
55
46
935

Explicație

$C = 2$, deci se va rezolva doar cerința $2$. Cu roșu am notat elementele corespunzătoare matricei $P$.

• Prima submatrice are colțul stânga-sus $(1, 1)$ și colțul dreapta-jos $(2, 2)$. Matricea $B$ a acestei submatrici este egală cu $\begin{pmatrix} 1 & 2 \\ 6 & 7 \end{pmatrix}$. După ce se efectuează înmulțirile corespunzătoare, aceasta devine $\begin{pmatrix} 1 \cdot \color{red}{1} & 2 \cdot \color{red}{2} \\ 6 \cdot \color{red}{2} & 7 \cdot \color{red}{4} \end{pmatrix} = \begin{pmatrix} 1 & 4 \\ 12 & 28 \end{pmatrix}$. Suma elementelor acestei matrici este egală cu $1 + 4 + 12 + 28$ = $45$.
• A doua submatrice are colțul stânga-sus $(3, 3)$ și colțul dreapta-jos $(4, 5)$. Matricea $B$ a acestei submatrici este egală cu $\begin{pmatrix} 3 & 2 & 1 \\ 8 & 7 & 6 \end{pmatrix}$. După ce se efectuează înmulțirile corespunzătoare, aceasta devine $\begin{pmatrix} 3 \cdot \color{red}{1} & 2 \cdot \color{red}{2} & 1 \cdot \color{red}{3} \\ 8 \cdot \color{red}{2} & 7 \cdot \color{red}{4} & 6 \cdot \color{red}{6} \end{pmatrix} = \begin{pmatrix} 3 & 4 & 3 \\ 16 & 28 & 36 \end{pmatrix}$. Suma elementelor acestei matrici este egală cu $3 + 4 + 3 + 16 + 28 + 36$ = $90$.