Se dă o matrice cu m linii şi n coloane, cu elementele numere naturale nenule şi un număr natural nenul fixat k.

Cerință

Pentru matricea dată şi numărul k dat să se răspundă la q întrebări de forma: “Câte submatrice pătratice de latură L cu cel mai mare divizor comun al elementelor egal cu k există în matricea dată?”

Date de intrare

Fișierul 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.

Date de ieșire

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.

Restricții și precizări

• 1 ≤ n, m ≤ 1002
• 1 ≤ q ≤ 50002
• 1 ≤ k ≤ 109+2
• Elementele matricei sunt numere naturale nenule mai mici sau egale decât 109+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.

Exemplu:

xcmmdc.in

3 3 3 4
3 6 2
9 12 3
2 6 3
2
1
3
2

xcmmdc.out

2
3
0
2

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.