Rôbot

Cho một bảng số nguyên dương \(A\) gồm \(N\) hàng và \(M\) cột, cùng một số nguyên dương \(K\).
Ô ở hàng \(i\), cột \(j\) có giá trị là \(A_{i,j}\).

Một robot bắt đầu tại ô \((1,1)\) và cần di chuyển đến ô \((N,M)\).
Khi đang ở ô \((i,j)\), robot chỉ có thể di chuyển sang một trong ba ô sau (nếu tồn tại):

• \((i, j+1)\);
• \((i+1, j)\);
• \((i+1, j+1)\).

Bạn được cho \(Q\) truy vấn. Mỗi truy vấn gồm một số nguyên \(X\) \((0 \le X < K)\).

Với mỗi truy vấn, hãy xác định số lượng ô nhiều nhất mà robot có thể đi qua trên một đường đi từ \((1,1)\) đến \((N,M)\) sao cho các ô đó thỏa mãn:
$
A_{i,j} \bmod K = X.
$

\InputFile
Dòng đầu chứa bốn số nguyên dương \(N, M, Q, K\)
\((1 \le N, M \le 500,\ 1 \le Q \le 10^5,\ 1 \le K \le 10^9)\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên dương, mô tả bảng \(A\)
\((1 \le A_{i,j} \le 10^9)\).

\(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(X\) là truy vấn tương ứng.

\OutputFile
Gồm \(Q\) dòng, mỗi dòng in ra một số nguyên là kết quả của truy vấn tương ứng.

Subtasks

• Subtask 1 (20 points): \(M = 1\).
• Subtask 2 (20 points): \(M = 2,\ Q \le 1000\).
• Subtask 3 (30 points): \(N, M, K \le 300\).
• Subtask 4 (30 points): Không có ràng buộc thêm.

Example

3 4 2 6
1 1 1 7
2 8 9 1
1 3 4 2
1
2

5
3