Live Archive 4478

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#define FOR(i,A) for(typeof A.begin() i = A.begin() ; i != A.end() ; i++)
#define all( v ) v.begin() , v.end()
#define rall( v ) v.rbegin() , v.rend()
#define clr( x , y ) memset( x , y , sizeof x )
#define mp make_pair
#define debug(x) cout << #x << " = " << x << endl
#define TAM 1010

using namespace std ;

typedef pair<int,int> ii ;
typedef pair<int,ii> pii ;
typedef long long ll ;

int inf , sup ;
int n , m ;
int v[ TAM ][ TAM ] ;

int lado( int x , int y ){
    int izq = 0 , der = min( n - x , m - y ) - 1 ;

    while( izq <= der ){
        int diag = ( izq + der ) / 2 ;
        if( v[ x + diag ][ y + diag ] > sup )
            der = diag - 1 ;
        else
            izq = diag + 1 ;
    }
    return izq ;
}

int pos( int x ){
    int *id =(int *) lower_bound( v[ x ] , v[ x ] + m , inf );
    if ( id == NULL ) return -1;
    return id - v[ x ] ;
}

int main(){

    while( scanf("%d%d" , &n , &m ) == 2 ){
        if( n == m && m == 0 ) break ;

        for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ; j++) scanf("%d" , &v[ i ][ j ] ) ;

        int q ;
        scanf("%d" , &q ) ;
        for(int k = 0 ; k < q ; k++){
            scanf("%d%d" , &inf , &sup ) ;
            int mx = 0 ;
            for(int i = 0 ; i < n ; i++){
                int j = pos( i ) ;
                if( j < 0 ) break ;
                mx = max( mx , lado( i , j ) ) ;
            }
            printf("%d\n" , mx ) ;
        }
        printf("-\n" ) ;
    }
    return 0 ;
}