xcmmdc

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 submatrici pătratice de latură L cu cel mai mare divizor comun al elementelor egal cu k există în matricea dată?”

Date de intrare

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.

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
• Pentru 50% din teste 1 ≤ n, m ≤ 502
• 1 ≤ q ≤ 50 002
• $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

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.