Cho một bảng ô vuông gồm ~M~ hàng và ~N~ cột, các hàng được đánh số từ 1 đến ~M~, các cột được đánh số từ 1 đến ~N~, ô ở hàng ~i~ và cột ~j~ có giá trị là ~A_{i,j}~ (~1 \le i \le M, 1 \le j \le N~). Tại một ô ~(i, j)~ trong bảng có thể di chuyển đến một trong các ô ~(i + 1, j), (i, j + 1), (i + 1, j + 1)~ với điều kiện không được đi ra khỏi bảng.

Cho trước số nguyên dương ~K~ và ~Q~ truy vấn, mỗi truy vấn cho biết số nguyên dương ~x~ và yêu cầu tìm đường đi từ ô (1,1) đến ô ~(M, N)~ đi qua nhiều nhất các ô có giá trị chia ~K~ dư ~x~.

Tính số lượng các ô của mỗi truy vấn.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~M, N, K, Q~ (~1 \le M, N \le 1000, Q \le 10^5~);
• Dòng thứ ~i~ trong ~M~ dòng tiếp theo ghi ~N~ số nguyên dương của bảng có giá trị bé hơn ~10^9~;
• ~Q~ dòng cuối cùng, mỗi dòng ghi một số nguyên ~x~ (~0 \le x < K \le 10^9~).

Output

• Gồm ~Q~ dòng ghi lần lượt các kết quả của truy vấn.