(robothn.*)

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ị \(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 ô \((j + 1,i)\) 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.

Dữ liệu vào:

+ Dòng đầu tiên chứa bốn số nguyên dương \(n,m,q,k\ (n,m \leq 1000;1 \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 vượt 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 \leq x < k)\) của mỗi thử thách.

Kết quả:

+ 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.

Ví dụ:

Ràng buộc:

+ Có 20% số test ứng với 20% số điểm thỏa mãn: \(n = 2\);

+ Có 20% số test khác ứng với 20% số điểm thỏa mãn: \(n = 2;q \leq 10^{3}\);

+ Có 30% số test khác ứng với 30% số điểm thỏa mãn: \(n,m,k \leq 300\);

+ Có 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.