== include(page="template/taskheader" task_id="xcmmdc") ==

Poveste şi cerinţă...

Se dă o matrice cu $m$ linii şi $n$ coloane, cu elementele numere naturale nenule şi un număr natural nenul fixat $k$.
 
h2. Cerinţă
 
Pentru matricea dată şi numărul $k$ dat să se răspundă la $q$ întrebări de forma: “Câte submatrici pătratice de latură $L$ cu cel mai mare divizor comun al elementelor egal cu $k$ există în matricea dată?”

h2. Date de intrare

Fişierul de intrare $xcmmdc.in$ ...

Fişierului de intrare $xcmmdc.in$ conţine pe prima linie patru numere naturale nenule separate prin câte un spaţiu: $m$ şi $n$ - numărul de linii şi numărul de coloane ale matricei, $k$ – numărul natural dat şi $q$ – numărul de întrebări. Pe următoarele $m$ linii se găsesc liniile matricei. Fiecare dintre aceste linii conţine câte $n$ numere naturale separate prin câte un spaţiu – elementele liniei corespunzătoare din matrice. Următoarele $q$ linii descriu întrebările. Fiecare dintre aceste linii conţine câte un număr natural $L$ – latura submatricei din întrebarea corespunzătoare.

h2. Date de ieşire

În fişierul de ieşire $xcmmdc.out$ ...

Fişierul de ieşire $xcmmdc.out$ va conţine $q$ linii. Pe fiecare dintre aceste linii se va scrie un singur număr natural reprezentând răspunsul la întrebarea corespunzătoare din fişierul de intrare.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* 1 ≤ $n$, $m$ ≤ 1002
* Pentru 50% din teste 1 ≤ $n$, $m$ ≤ 502
* 1 ≤ $q$ ≤ 50002
* 1 ≤ $k$ ≤ 10^9^ + 2
* Elementele matricei sunt numere naturale nenule mai mici sau egale decât 10^9^ + 2.
* 1 ≤ $L$ ≤ min($m$, $n$) pentru fiecare întrebare
* Prin submatrice pătratică de latură $L$ se înţelege o matrice obţinută prin intersecţia a $L$ linii consecutive cu $L$ coloane consecutive din matrice.

h2. Exemplu
table(example). |_. xcmmdc.in |_. xcmmdc.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3 3 4
3 6 2
9 12 3
2 6 3
2
1
3
2
| 2
3
0
2

|
h3. Explicaţie

...

Pentru prima şi ultima întrebare avem două submatrice:
3 6
9 12
-----
12 3
6 3
Prima submatrice se obţine prin intersecţia primelor două linii cu primele două coloane, iar a doua prin intersecţia ultimelor două linii cu
ultimele două coloane.
 

== include(page="template/taskfooter" task_id="xcmmdc") ==