Untitled

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define test cout<<"ok"<<endl; 
#define check(n) for(auto x:n)cout<<x<<" "
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int find_left(int i, int x,int target, vector < int > a[]){ 
    int ans = -1;
    int low  = x; 
    int high = x + i;
    while(low <= high){
        ll mid = (low + high) /2;
        if(a[mid][mid - x] >= target){
            high = mid -1;
            ans  = mid;
        }
        else
            low = mid +1;
        
    }    
    return ans;
}// this is for find the left valid cell till major diagonal

int find_left2(int i, int y,int target, vector < int > a[]){
    int ans = -1;
    int low  = y; 
    int high = y + i;
    while(low <= high){
        ll mid = (low + high) /2;
        if(a[mid - y][mid] >= target){
            high = mid -1;
            ans  = mid;
        }
        else
            low = mid +1;
        
    }    
    return ans;
} // this is for find the left valid cell after the major digonal

int find_right(int i, int x,int target, vector < int > a[]){
    int low  = x; 
    int high = x + i;
    ll ans = -1;
    while(low <= high){
        ll mid = (low + high) /2;
        if(a[mid][mid - x] <= target){
            low = mid +1;
            ans = mid;  
        }
        else
            high = mid -1;
        
    }  
    return ans;  
} // this is for right cell till major digonal

int find_right2(int i, int y,int target, vector < int > a[]){
    int low  = y; 
    int high = y + i;
    ll ans = -1;
    while(low <= high){
        ll mid = (low + high) /2;
        if(a[mid-y][mid] <= target){
            low = mid +1;
            ans = mid;  
        }
        else
            high = mid -1;
        
    }  
    return ans;  
}//this is for right cell after major digonal

int dis(int i, int x, vector < int > a[], int L, int U){
    int leftindex = find_left(i,x,L,a);
    int rightindex = find_right(i,x,U,a);
       
    if((leftindex > rightindex) || leftindex == -1 || rightindex == -1)
        return 0;
    else 
        return (rightindex - leftindex) +1;
} // this is for find all the distance till major diagonal

int dis2(int i, int x, vector < int > a[], int L, int U){
    int leftindex = find_left2(i,x,L,a);
    int rightindex = find_right2(i,x,U,a);
    

    if((leftindex > rightindex) || leftindex == -1 || rightindex == -1)
        return 0;
    else 
        return (rightindex - leftindex) +1;
    
} // this is for find all the distance after major digonal

int main(){
    Faster;
    int n, m;
    while(cin  >> n >> m){
        if(n == 0 && m == 0)
            break;
        int mx = max(n,m); // consider the maximum size of 2D array 
        vector <int > a[mx]; // declare the maximum size of array
        for(int i = 0; i< mx; i++)
        {
            for(int j =0; j < mx; j++)
               a[i].push_back(INT_MAX); // fill all the cell with maximum integer 
                                        // all extra cell is filled up with the maximum value
        }
        
       
       for(int i = 0; i < n; i++)
       {
        for(int j = 0; j < m; j++)
            {
                int x; cin >> x;
                a[i][j] = x;
            }
        } 
        
        

    int q;
    cin >> q;

    while(q--){
        int L ,U;
        int ans = 0;
        cin >> L >> U;
        int x = mx-1;
        int y = 0;
        for(int i = 0; i< mx; i++)
        {
            
            ans  = max(dis(i,x,a,L,U), ans); 
            x--;
        }
        y = 1;
     
        for(int i = mx -2; i >= 0; i--){
            ans = max(ans, dis2(i,y,a,L,U));
            y++;
            
        }
        cout << ans << endl;
        

    }
    cout << "-" << endl;
}

}