Mapat

Dacă ești doar curios, vei vedea un puzzle. Dacă ești disperat, vei vedea un labirint. Dar dacă ai răbdare, îi vei descoperi magia.
– Ernő Rubik

Pentru a descoperi ieșirea din Marele Labirint, exploratorul trebuie să descifreze o hartă antică. Harta este reprezentată sub forma unui tablou bidimensional cu $N$ linii și $M$ coloane, cu elemente numere naturale nenule. Liniile sunt numerotate de la $1$ la $N$ (de sus în jos), iar coloanele de la $1$ la $M$ (de la stânga la dreapta).

Definim un mapat ca fiind un pătrat descris de o poziție $(i, j)$ numită colț principal și o latură de lungime $L$, unde $1 \le L \le \min(i, j)$. Mapatul acoperă toate celulele având indicii $(x, y)$, unde $i - L + 1 \le x \le i$ și $j - L + 1 \le y \le j$, adică este un pătrat de $L \times L$ celule al cărui colț dreapta-jos este chiar $(i, j)$.

Valoarea unui mapat se calculează astfel:

1. Se determină suma tuturor elementelor din pătrat, notată cu $S$.
2. Valoarea mapatului este produsul dintre $S$ și valoarea de la poziția $(i, j)$.

De exemplu, considerând tabloul de mai jos:

un mapat cu colțul principal la poziția $(2, 3)$ și $L = 2$ acoperă celulele de la pozițiile $(1, 2), (1, 3), (2, 2), (2, 3)$. Deci, $S = 1 + 2 + 3 + 2 = 8$ și valoarea mapatului este $8 \times 2 = 16$.

Fixând o lungime $L$ și o linie $i$ (cu $i \ge L$), pentru fiecare coloană $j \ge L$, notăm cu $A_j$ valoarea mapatului cu colțul principal la coordonatele $(i, j)$ și latura de lungime $L$. O secvență de mapate situate pe linia $i$ este determinată de doi indici, $st$ și $dr$. Definim suma secvenței de mapate ca fiind $A_{st} + A_{st+1} + \dots + A_{dr}$, cu $L \le st \le dr \le M$.

Cerințe

Se dau $q$ întrebări de tipul 1 și $p$ întrebări de tipul 2.

1. Întrebare de tipul 1. Cunoscându-se trei valori $L$, $i$ și $maxVal$, determinați lungimea maximă a unei secvențe de mapate cu latura de lungime $L$, situate pe linia $i$ și având suma secvenței de mapate mai mică sau egală cu $maxVal$.
2. Întrebare de tipul 2. Cunoscându-se patru valori $L$, $i$, $minVal$ și $maxVal$, determinați numărul secvențelor de mapate cu latura de lungime $L$, situate pe linia $i$ și având suma secvenței de mapate cuprinsă între $minVal$ și $maxVal$.

Date de intrare

Fișierul de intrare mapat.in conține:

• Pe prima linie patru numere naturale $N, M, q, p$.
• Pe următoarele $N$ linii câte $M$ numere naturale, reprezentând elementele tabloului bidimensional.
• Următoarele $q$ linii conțin fiecare câte trei numere: $L$, $i$, $maxVal$ (corespunzătoare întrebărilor de tipul 1).
• Ultimele $p$ linii conțin fiecare câte patru numere: $L$, $i$, $minVal$, $maxVal$ (corespunzătoare întrebărilor de tipul 2).
  Valorile de pe fiecare linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire mapat.out va conține:

• Pe primele $q$ linii câte un număr natural reprezentând răspunsul la fiecare întrebare de tipul 1, în ordinea în care acestea apar în fișierul de intrare.
• Pe următoarele $p$ linii câte un număr natural reprezentând răspunsul la fiecare întrebare de tipul 2, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

• $1 \le N, M \le 1000$;
• Elementele tabloului sunt numere naturale nenule $\le 400$.
• $1 \le p + q \le 8000$;
• $1 \le i \le N$, iar $i \ge L$ pentru orice întrebare.
• $1 \le L \le \min(N, M)$;
• $0 \le minVal < maxVal < 10^{15}$ pentru orice întrebare de tipul 2.
• $0 < maxVal < 10^{15}$ pentru orice întrebare de tipul 1.

Exemplul 1

mapat.in

4 4 2 0
1 3 5 2
4 3 1 2
7 8 1 1
2 2 3 1
2 4 20
1 4 16

mapat.out

1
3

Explicație

Avem $q = 2$ întrebări de tipul 1:
Întrebarea 1: $L = 2$, $i = 4$, $maxVal = 20$. Calculăm $A_j$ pentru $j \ge 2$ pe linia 4:
$A_2 = (7 + 8 + 2 + 2) \times 2 = 19 \times 2 = 38$, $A_3 = (8 + 1 + 2 + 3) \times 3 = 14 \times 3 = 42$ și $A_4 = 6$. Singura secvență cu suma mai mică sau egală ca 20 este secvența $[4, 4]$, deci răspunsul este 1.
Întrebarea 2: $L = 1$, $i = 4$, $maxVal = 16$.
$A_1 = 2 \times 2 = 4, A_2 = 2 \times 2 = 4, A_3 = 3 \times 3 = 9, A_4 = 1 \times 1 = 1$.
Lungimea maximă a unei secvențe de mapate este 3, găsită pentru secvența $[2, 4]$, deci răspunsul este 3.

Exemplul 2

mapat.in

4 4 0 2
1 3 5 2
4 3 1 2
7 8 1 1
2 2 3 1
2 2 5 30
1 4 7 16

mapat.out

2
5

Explicație

Avem $p = 2$ întrebări de tipul 2:
Întrebarea 1: $L = 2$, $i = 2$, $minVal = 5$, $maxVal = 30$. Avem $A_2 = 33$, $A_3 = 12$, $A_4 = 20$. Secvențele de mapate cu suma cuprinsă între $minVal$ și $maxVal$ sunt cele care au capetele la pozițiile $[3, 3]$ și $[4, 4]$, deci răspunsul este 2.
Întrebarea 2: $L = 1$, $i = 4$, $minVal = 7$, $maxVal = 16$.
$A_1 = 4, A_2 = 4, A_3 = 9, A_4 = 1$. Secvențele de mapate cu suma cuprinsă între $minVal$ și $maxVal$ sunt cele care au capetele la pozițiile: $[1, 2], [2, 3], [2, 4], [3, 3]$ și $[3, 4]$, deci răspunsul este 5.