Có một bản đồ dạng lưới ô vuông gồm ~N~ dòng và ~M~ cột, các dòng đánh số từ trên xuống dưới, từ ~1~ đến ~N~; các cột đánh số từ trái sang phải, từ ~1~ đến ~M~; ô ở dòng thứ ~i~ và cột thứ ~j~ được gọi là ô ~(i, j)~ và có giá trị là ~A(i, j)~.

Robot đang ở ô ~(1, 1)~, cần di chuyển đến ô ~(N, M)~. Tuy nhiên, trong mỗi lượt di chuyển, nếu robot ở ô ~(i, j)~, chỉ được phép di chuyển sang ô ~(i, j + 1)~ hoặc ô ~(i + 1, j)~ hoặc ô ~(i + 1, j + 1)~.

Cho một số nguyên dương ~K~. Robot có ~Q~ thử thách, trong thử thách thứ ~i~, cho một số nguyên ~x~ và robot cần di chuyển từ ô ~(1, 1)~ tới ô ~(N, M)~ sao cho đi qua nhiều nhất các ô có giá trị chia ~K~ dư ~x~.

Yêu cầu: Hãy giúp robot đưa ra số lượng ô nhiều nhất có thể đi qua thỏa mãn yêu cầu đề bài.

Input

• Dòng đầu chứa bốn số nguyên dương ~N, M, Q, K~ (~N, M \le 1000~; ~Q \le 10^5~; ~K \le 10^6~) tương ứng là kích thước của lưới ô vuông, số lượng thử thách và số ~K~ cho trước;
• ~N~ dòng sau, mỗi dòng chứa ~M~ số nguyên dương mô tả các giá trị của bản đồ lưới ô vuông. Các số có giá trị không quá ~10^9~;
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên mô tả số ~x~ (~0 \le x < K~) của mỗi thử thách.

Output

Gồm ~Q~ dòng, mỗi dòng gồm một số nguyên là số lượng ô nhiều nhất thỏa mãn yêu cầu đề bài.

Sample Input 1

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

Sample Output 1

5
3

Giải thích:

• Thử thách 1: Tìm cách đi sao cho đi qua nhiều nhất các ô chia 6 dư 1. Có thể đi theo cách sau: đi qua các ô 1, 1, 1, 7, 1. Có 5 giá trị thỏa mãn.
• Thử thách 2: Tìm cách đi sao cho đi qua nhiều nhất các ô chia 6 dư 2. Có thể đi theo cách sau: đi qua các ô 2, 8, 2. Có 3 giá trị thỏa mãn.

Subtasks

• Có 20% số test ứng với 20% số điểm có ~N = 1~;
• 20% số test ứng với 20% số điểm có ~N = 2~; ~Q \le 10^3~;
• 30% số test ứng với 30% số điểm có ~N, M, K \le 300~;
• 30% số test còn lại với 30% số điểm không có ràng buộc gì thêm.