Peluzasud

Eroul Mishu trebuie să recupereze legendara sabie cu lunetă din castelul Peluzasud pentru a o învinge pe vrăjitoarea malefică Mirinda. Peluzasudul este organizat pe $9$ nivele, fiecare nivel fiind reprezentat de o matrice de dimensiuni $N \times M$. Pe lângă arma legendară, în castel mai există și $N \times M$ monștri de diferite puteri, exprimate prin numere naturale. Așezarea acestora în castel respectă $3$ reguli:

1. Un monstru cu puterea $x$ se va afla mereu pe nivelul egal cu numărul de cifre ale lui $x$.
2. Nu vor exista 2 monștri în aceeași celulă $(i, j, k)$.
3. Nu va exista un monstru deasupra altui monstru. Cu alte cuvinte, dacă celula $(i, j, x)$ este ocupată de un monstru, atunci oricare ar fi $y ≠ x$, celula $(i, j, y)$ va rămâne neocupată.

Din moment ce sunt $N \times M$ inamici care nu pot fi așezați unul deasupra celuilalt, se observă că monștrii pot fi, la rândul lor, reprezentați sub forma unei matrici $N \times M$, unde valoarea elementului $(i, j)$ determină atât puterea monstrului cât și nivelul pe care acesta se află.

Cerințe

După ce Mishu a primit această matrice de la Înțeleptul DCIT, acesta vrea să știe:

1. Suma puterilor monștrilor de pe nivelul $k$.
2. Răspunsurile la $Q$ întrebări de forma: “Care este suma puterilor monștrilor de pe nivelul $k$ din submatricea cu vârfurile stânga-sus în $(a, b)$ și dreapta-jos în $(c, d)$?”.

Ajutați-l pe Mishu să salveze lumea!

Date de intrare

Pe prima linie a fișierului peluzasud.in se va găsi un număr natural $c$, reprezentând cerința care trebuie rezolvată.

Pe a doua linie vor fi 2 numere naturale, $N$ și $M$, reprezentând dimensiunile matricei.

Pe următoarele $N$ linii se vor găsi $M$ numere, elementele matricei.

Dacă $c = 1$, pe ultima linie se va găsi un număr $k$, nivelul care îl interesează pe Mishu

Dacă $c = 2$, pe linia $N + 2$ va fi numărul natural $Q$, reprezentând numărul de întrebări pentru care Mishu vrea răspuns, iar pe următoarele $Q$ linii vor fi câte $5$ numere, $a, b, c, d, k$, întrebările sale.

Date de ieșire

Dacă $c = 1$, fișierul peluzasud.out va conține un singur număr, suma cerută.

Dacă $c = 2$, fișierul va conține $Q$ numere, câte unul pe fiecare linie, reprezentând răspunsurile la întrebări.

Restricții și precizări

• $1 \le N, M ≤⁢ 10^3$;
• $1 \le Q \le 2 \cdot 10^5$;
• $c ∈ \{1, 2\}$;
• $1 \le k \le 9$;
• Elementele matricei vor fi numere naturale din intervalul $[1, 10^9-1]$.

Exemplul 1

peluzasud.in

1
5 6
7 18 2 124 3344 48
88 19 5 7 443 25
1129 63 393 9 5684 199
37 42 9981 2 13 1001
743 1000 808 1 63 6
3

peluzasud.out

2710

Explicație

Numerele de pe nivelul $3$ (de $3$ cifre) sunt $124, 443, 393, 199, 808, 743$.
$124 + 443 + 393 + 199 + 808 + 743 = 2710$

Exemplul 2

peluzasud.in

2
5 6
7 18 2 124 3344 48
88 19 5 7 443 25
1129 63 393 9 5684 199
37 42 9981 2 13 1001
743 1000 808 1 63 6
5
2 2 5 6 3
1 1 3 4 2
5 6 5 6 1
3 4 4 6 4
2 2 4 4 1

peluzasud.out

1843
188
6
6685
23

Explicație

Pentru prima întrebare, numerele de $3$ cifre din submatricea $(2, 2)$, $(5, 6)$ sunt $443, 393, 199$ și $808$.
$443 + 393 + 199 + 808 = 1843$

Pentru a doua întrebare, numerele de $2$ cifre din submatricea $(1, 1)$, $(3, 4)$ sunt $18, 88, 19$ și $63$.
$18 + 88 + 19 + 63 = 188$