Robot

Cho một bảng số nguyên dương A có N hàng, M cột và một số nguyên dương K. Số nằm ở hàng $i$, cột $j$ có tọa độ là $(i, j)$ và có giá trị là $A_{ij}$. Một con robot đang đứng ở ô $(1, 1)$ và cần di chuyển đến ô $(M, N)$. Khi đứng ở ô $(i, j)$, robot chỉ có thể di chuyển vào ba ô $(i, j+1)$, $(i+1, j)$ hoặc $(i+1, j+1)$.

Cho Q truy vấn, mỗi truy vấn gồm một số tự nhiên $X$ ($X < K$). Với mỗi truy vấn, hãy cho biết đường đi của robot từ ô $(1, 1)$ đến ô $(M, N)$ có thể đi qua nhiều nhất bao nhiêu ô $(i, j)$ thỏa mãn $A_{ij} \bmod K = X$.

Yêu cầu: Hãy trả lời Q truy vấn của đề bài.

Dữ liệu vào từ tệp văn bản ROBOT.INP:

• Dòng đầu tiên chứa bốn số nguyên dương $N, M, Q, K$ ($1 \le N, M \le 1000, 1 \le Q \le 10^5, 1 \le K \le 10^9$).
• Trong N dòng tiếp theo, dòng thứ $i$ chứa M số nguyên dương biểu diễn bảng $A$ ($1 \le A_{ij} \le 10^9$).
• Trong Q dòng tiếp theo, mỗi dòng chứa một số tự nhiên $X$ thể hiện truy vấn tương ứng.

Kết quả ghi ra tệp văn bản ROBOT.OUT:

• Gồm Q dòng, mỗi dòng chứa một số tự nhiên là kết quả của truy vấn tương ứng.

• Có 20% số test tương ứng 20% số điểm có $M = 1$.
• 20% số test tương ứng 20% số điểm có $M = 2, Q \le 1000$.
• 30% số test tương ứng 30% số điểm có $M, N, M \le 300$.
• 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm.