/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
// your code goes here
String[]size
=(in.
readLine().
trim()).
split("\\s+"); int rows
=Integer.
parseInt(size
[0]); int colums
=Integer.
parseInt(size
[1]); int[][]matrix=new int[rows][colums];
for (int i = 0; i <rows ; i++) {
String[]elements
=(in.
readLine().
trim()).
split("\\s+"); for (int j = 0; j <colums ; j++) {
matrix
[i
][j
]=Integer.
parseInt(elements
[j
]); }
}
int[][]precomput=precomputation(matrix);
int min=1;
int max
=Math.
min(rows,colums
); int t
=Integer.
parseInt(in.
readLine().
trim()); while (t!=0){
int threshold
=Integer.
parseInt(in.
readLine().
trim()); System.
out.
println(sizeofsquare
(precomput,min,max,threshold
)); t--;
}
}
static int sizeofsquare(int[][]precomput,int min,int max,int threshold){
while (min<=max){
int mid=min+(max-min)/2;
if (ifpossible(mid,precomput,threshold)) {
if (!ifpossible(mid+1,precomput,threshold)){
return mid;
}else min=mid+1;
}else {
max=mid-1;
}
}
return 0;
}
static boolean ifpossible(int size,int[][]precomput,int threshold){
for (int i = 0; i <precomput.length-size ; i++) {
for (int j = 0; j <precomput[i].length-size ; j++) {
if (sum(precomput,i,j,i+size-1,j+size-1)<=threshold){
return true;
}
}
}
return false;
}
static long sum(int[][]precomput,int i1,int j1,int i2,int j2){
long ans=precomput[i2][j2];
if (j1-1>=0) {
ans -= precomput[i2][j1 - 1];
if (i1-1>=0){
ans-=precomput[i1-1][j2];
ans+=precomput[i1-1][j1-1];
}
}else {
if (i1-1>=0){
ans-=precomput[i1-1][j2];
}
}
return ans;
}
static int[][]precomputation(int[][]arr){
int n=arr.length;
int m=arr[0].length;;
int [][]ans=new int[n][m];
//rowwise
for (int i = 0; i <n ; i++) {
ans[i][0]=arr[i][0];
for (int j = 1; j <m ; j++) {
ans[i][j]=ans[i][j-1]+arr[i][j];
}
}
//columnwise
for (int j = 0; j <m ; j++) {
for (int i = 1; i <n ; i++) {
ans[i][j]+=ans[i-1][j];
}
}
return ans;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCQlCdWZmZXJlZFJlYWRlciBpbj1uZXcgQnVmZmVyZWRSZWFkZXIobmV3IElucHV0U3RyZWFtUmVhZGVyKFN5c3RlbS5pbikpOwogICAgICAgIFN0cmluZ1tdc2l6ZT0oaW4ucmVhZExpbmUoKS50cmltKCkpLnNwbGl0KCJcXHMrIik7CiAgICAgICAgaW50IHJvd3M9SW50ZWdlci5wYXJzZUludChzaXplWzBdKTsKICAgICAgICBpbnQgY29sdW1zPUludGVnZXIucGFyc2VJbnQoc2l6ZVsxXSk7CiAgICAgICAgaW50W11bXW1hdHJpeD1uZXcgaW50W3Jvd3NdW2NvbHVtc107CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPHJvd3MgOyBpKyspIHsKICAgICAgICAgICAgU3RyaW5nW11lbGVtZW50cz0oaW4ucmVhZExpbmUoKS50cmltKCkpLnNwbGl0KCJcXHMrIik7CiAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDxjb2x1bXMgOyBqKyspIHsKICAgICAgICAgICAgICAgIG1hdHJpeFtpXVtqXT1JbnRlZ2VyLnBhcnNlSW50KGVsZW1lbnRzW2pdKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpbnRbXVtdcHJlY29tcHV0PXByZWNvbXB1dGF0aW9uKG1hdHJpeCk7CiAgICAgICAgaW50IG1pbj0xOwogICAgICAgIGludCBtYXg9TWF0aC5taW4ocm93cyxjb2x1bXMpOwogICAgICAgIGludCB0PUludGVnZXIucGFyc2VJbnQoaW4ucmVhZExpbmUoKS50cmltKCkpOwogICAgICAgIHdoaWxlICh0IT0wKXsKICAgICAgICAgICAgaW50IHRocmVzaG9sZD1JbnRlZ2VyLnBhcnNlSW50KGluLnJlYWRMaW5lKCkudHJpbSgpKTsKICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHNpemVvZnNxdWFyZShwcmVjb21wdXQsbWluLG1heCx0aHJlc2hvbGQpKTsKICAgICAgICAgICAgdC0tOwogICAgICAgIH0KCX0KCXN0YXRpYyBpbnQgc2l6ZW9mc3F1YXJlKGludFtdW11wcmVjb21wdXQsaW50IG1pbixpbnQgbWF4LGludCB0aHJlc2hvbGQpewogICAgICAgIHdoaWxlIChtaW48PW1heCl7CiAgICAgICAgICAgaW50IG1pZD1taW4rKG1heC1taW4pLzI7CiAgICAgICAgICAgaWYgKGlmcG9zc2libGUobWlkLHByZWNvbXB1dCx0aHJlc2hvbGQpKSB7CiAgICAgICAgICAgICAgIGlmICghaWZwb3NzaWJsZShtaWQrMSxwcmVjb21wdXQsdGhyZXNob2xkKSl7CiAgICAgICAgICAgICAgICAgICByZXR1cm4gbWlkOwogICAgICAgICAgICAgICB9ZWxzZSBtaW49bWlkKzE7CiAgICAgICAgICAgfWVsc2UgewogICAgICAgICAgICAgICBtYXg9bWlkLTE7CiAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gMDsKICAgIH0KICAgIHN0YXRpYyBib29sZWFuIGlmcG9zc2libGUoaW50IHNpemUsaW50W11bXXByZWNvbXB1dCxpbnQgdGhyZXNob2xkKXsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPHByZWNvbXB1dC5sZW5ndGgtc2l6ZSA7IGkrKykgewogICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8cHJlY29tcHV0W2ldLmxlbmd0aC1zaXplIDsgaisrKSB7CiAgICAgICAgICAgICAgICBpZiAoc3VtKHByZWNvbXB1dCxpLGosaStzaXplLTEsaitzaXplLTEpPD10aHJlc2hvbGQpewogICAgICAgICAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KICAgIHN0YXRpYyBsb25nIHN1bShpbnRbXVtdcHJlY29tcHV0LGludCBpMSxpbnQgajEsaW50IGkyLGludCBqMil7CiAgICAgICAgbG9uZyBhbnM9cHJlY29tcHV0W2kyXVtqMl07CiAgICAgICAgaWYgKGoxLTE+PTApIHsKICAgICAgICAgICAgYW5zIC09IHByZWNvbXB1dFtpMl1bajEgLSAxXTsKICAgICAgICAgICAgaWYgKGkxLTE+PTApewogICAgICAgICAgICAgICAgYW5zLT1wcmVjb21wdXRbaTEtMV1bajJdOwogICAgICAgICAgICAgICAgYW5zKz1wcmVjb21wdXRbaTEtMV1bajEtMV07CiAgICAgICAgICAgIH0KCiAgICAgICAgfWVsc2UgewogICAgICAgICAgICBpZiAoaTEtMT49MCl7CiAgICAgICAgICAgICAgICBhbnMtPXByZWNvbXB1dFtpMS0xXVtqMl07CiAgICAgICAgICAgIH0KCiAgICAgICAgfQogICByZXR1cm4gYW5zOwogICAgfQogICAgc3RhdGljIGludFtdW11wcmVjb21wdXRhdGlvbihpbnRbXVtdYXJyKXsKICAgICAgICBpbnQgbj1hcnIubGVuZ3RoOwogICAgICAgIGludCBtPWFyclswXS5sZW5ndGg7OwogICAgICAgIGludCBbXVtdYW5zPW5ldyBpbnRbbl1bbV07CiAgICAgICAgLy9yb3d3aXNlCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPG4gOyBpKyspIHsKICAgICAgICAgICAgYW5zW2ldWzBdPWFycltpXVswXTsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDE7IGogPG0gOyBqKyspIHsKICAgICAgICAgICAgICAgIGFuc1tpXVtqXT1hbnNbaV1bai0xXSthcnJbaV1bal07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgLy9jb2x1bW53aXNlCiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPG0gOyBqKyspIHsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPG4gOyBpKyspIHsKICAgICAgICAgICAgICAgIGFuc1tpXVtqXSs9YW5zW2ktMV1bal07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGFuczsKCiAgICB9Cn0=