„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 𝑁 linii și 𝑀 coloane, cu elemente numere naturale nenule. Liniile sunt numerotate de la 1 la 𝑁 (de sus în jos), iar coloanele de la 1 la 𝑀 (de la stânga la dreapta).

Definim un mapat ca fiind un pătrat descris de o poziție (𝑖,𝑗) numită colț principal și o latură de lungime 𝐿, unde 1 ≤ 𝐿 ≤ min(𝑖, 𝑗). Mapatul acoperă toate celulele având indicii (𝑥,𝑦), unde 𝑖 − 𝐿 + 1 ≤ 𝑥 ≤ 𝑖 și 𝑗 − 𝐿 + 1 ≤ 𝑦 ≤ 𝑗, adică este un pătrat de 𝐿 × 𝐿 celule al cărui colt, dreapta-jos este chiar (𝑖,𝑗).

Valoarea unui mapat se calculează astfel:

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

De exemplu, considerând tabloul de mai jos:

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

Fixând o lungime 𝐿 și o linie 𝑖 (cu 𝑖 ≥ 𝐿), pentru fiecare coloană 𝑗 ≥ 𝐿, notăm cu 𝐴[𝑗] valoarea mapatului cu colțul principal la coordonatele (𝑖,𝑗) și latura de lungime 𝐿. O secvență de mapate situate pe linia i este determinată de doi indici, 𝑠𝑡 și 𝑑𝑟. Definim suma secvenței de mapate ca fiind 𝐴[𝑠𝑡] + 𝐴[𝑠𝑡 +1] + ··· + 𝐴[𝑑𝑟] , cu 𝐿 ≤ 𝑠𝑡 ≤ 𝑑𝑟 ≤ 𝑀.

Cerința

Se dau 𝑞 întrebări de tipul 1 și 𝑝 întrebări de tipul 2.

1. Întrebare de tipul 1. Cunoscându-se trei valori 𝐿, 𝑖 și maxVal, determinați lungimea maximă a unei secvențe de mapate cu latura de lungime 𝐿, situate pe linia 𝑖 și având suma secvenței de mapate mai mică sau egală cu maxVal.
2. Întrebare de tipul 2. Cunoscându-se patru valori 𝐿, 𝑖, minVal și maxVal, determinați numărul secvențelor de mapate cu latura de lungime 𝐿, situate pe linia 𝑖 ș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 𝑁 𝑀 𝑞 𝑝.
• Pe următoarele 𝑁 linii câte 𝑀 numere naturale, reprezentând elementele tabloului bidimensional.
• Următoarele 𝑞 linii conțin fiecare câte trei numere: 𝐿 𝑖 maxVal (corespunzătoare întrebărilor de tipul 1).
• Ultimele 𝑝 linii conțin fiecare câte patru numere: 𝐿 𝑖 minVal maxVal (corespunzătoare întrebărilor de tipul 2).

Date de ieșire

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

• Pe primele 𝑞 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 𝑝 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 ≤ 𝑁 , 𝑀 ≤ 1000;
• Elementele tabloului sunt numere naturale nenule ≤ 400.
• 1 ≤ 𝑝 + 𝑞 ≤ 8000;
• 1 ≤ 𝑖 ≤ 𝑁 , iar 𝑖 ≥ 𝐿 pentru orice întrebare.
• 1 ≤ 𝐿 ≤ min(𝑁 , 𝑀);
• 0 ≤ minVal < maxVal < 1015 pentru orice întrebare de tipul 2.
• 0 < maxVal < 1015 pentru orice întrebare de tipul 1.

Subtaskuri

Există subtaskuri în care:

• 𝑁,𝑀 ≤ 50, 𝑝 = 0 (există doar întrebări de tipul 1);
• 𝑁,𝑀 ≤ 1000, 𝑝 = 0 (există doar întrebări de tipul 1);
• 𝑁,𝑀 ≤ 50, 𝑞 = 0 (există doar întrebări de tipul 2);
• 𝑁,𝑀 ≤ 1000, 𝑞 = 0 (există doar întrebări de tipul 2);
• 𝑁,𝑀 ≤ 1000, 𝑝×𝑞 ≠ 0 (există întrebări de ambele tipuri).

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 𝑞 = 2 întrebări de tipul 1:
Întrebarea 1: 𝐿 = 2, 𝑖 = 4, maxVal = 20. Calculăm 𝐴[𝑗] pentru 𝑗 ≥ 2 pe linia 4:
𝐴[2] = (7+8+2+2)×2 = 19×2 = 38, 𝐴[3] = (8+1+2+3)×3 = 14×3 = 42 și 𝐴[4] = 6. Singura secvență cu suma mai mică sau egală ca 20 este secvența [4, 4], deci răspunsul este 1.

Întrebarea 2: 𝐿 = 1, 𝑖 = 4, maxVal = 16. 𝐴[1] = 2 × 2 = 4, 𝐴[2] = 2 × 2 = 4, 𝐴[3] = 3 × 3 = 9, 𝐴[4] = 1 × 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 𝑝 = 2 întrebări de tipul 2:

Întrebarea 1: 𝐿 = 2, 𝑖 = 2, minVal = 5, maxVal = 30. Avem 𝐴[2] = 33, 𝐴[3] = 12, 𝐴[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: 𝐿 = 1, 𝑖 = 4, minVal = 7, maxVal = 16. 𝐴[1] = 4, 𝐴[2] = 4, 𝐴[3] = 9, 𝐴[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.