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\).

Input

• Dòng đầu chứa bốn số nguyên dương \(N, M, Q, K\) \((N,M \leq 1000; Q \leq 10^5; K \leq 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 \(x\) \((0 \leq 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

Example

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

5
3

Scoring

• \(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 \leq 10^3\)
• \(30\%\) số test ứng với \(30\%\) số điểm có \(N, M, K \leq 300\)
• \(30\%\) số test còn lại với \(30\%\) số điểm không có ràng buộc gì thêm