1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int N = 1e3+10;
 7 int x1, y1, x2, y2, n, m;
 8 int a[N][N];
 9 int dp[10][10][N][N];
10 int Log[N];
11 int ask(int x1, int y1, int x2, int y2){
12     int k1 = Log[x2-x1+1], k2 = Log[y2-y1+1];
13     int ans = max(dp[k1][k2][x1][y1], dp[k1][k2][x1][y2-(1<<k2)+1]);
14     ans = max(ans, dp[k1][k2][x2-(1<<k1)+1][y1]);
15     ans = max(ans, dp[k1][k2][x2-(1<<k1)+1][y2-(1<<k2)+1]);
16     return ans;
17 }
18 bool test(int l){
19     //dp[0][x1][y1] dp[0][x2-x+1][y2-x+1]
20     int ret = ask(x1+l-1, y1+l-1, x2, y2);
21     return ret >= l;
22 }
23 void init(){
24     for(int i = 1; i <= Log[n]; i++)
25         for(int x = 1; x+(1<<i)-1 <= n; x++)
26             for(int y = 1; y <= m; y++)
27                 dp[i][0][x][y] = max(dp[i-1][0][x][y], dp[i-1][0][x+(1<<i-1)][y]);
28     for(int i = 0; i <= Log[n]; i++)
29         for(int j = 1; j <= Log[m]; j++)
30             for(int x = 1; x+(1<<i)-1 <= n; x++)
31                 for(int y = 1; y+(1<<j)-1 <= m; y++)
32                     dp[i][j][x][y] = max(dp[i][j-1][x][y], dp[i][j-1][x][y+(1<<j-1)]);
33 }
34 int main(){
35     for(int i = 2; i < N; i++) Log[i] = Log[i>>1]+1;
36     scanf("%d%d", &n, &m);
37     for(int i = 1; i <= n; i++)
38         for(int j = 1; j <= m; j++){
39             scanf("%d", &a[i][j]);
40             if(a[i][j] == 0) dp[0][0][i][j] = 0;
41             else{
42                 int len = min(dp[0][0][i-1][j], dp[0][0][i][j-1]);
43                 dp[0][0][i][j] = len+a[i-len][j-len];
44             }
45         }
46     init();
47 
48     int t; scanf("%d", &t);
49     while(t--){
50         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
51         int L = 0, R = min(x2-x1+1, y2-y1+1);
52         while(L < R){
53             int M = L+R+1 >> 1;
54             if( test(M) )
55                 L = M;
56             else
57                 R = M-1;
58         }
59         printf("%d\n", L);
60     }
61     return 0;
62 }