蒟蒻刚学整体二分，全WA求调

rt

#include<bits/stdc++.h>
using namespace std;

const int N = 505, Q = 1e6 + 5;

struct node{
    bool type;
    int x1, y1, x2, y2, k, id, ans;
} ask[Q], ask2[Q], ask3[Q];
int cnt;

int a[N][N], q, n;

struct treezu{
    int f[N][N];
    void add( int x, int y, int z ){
        for( int i = x; i <= n; i += ( i & ( -i ) ) )
            for( int j = y; j <= n; j += ( j & ( -j ) ) )
                f[i][j] += z;
    }
    int find( int x, int y ){
        if( x == 0 || y == 0 ) return 0;
        int ans = 0;
        for( int i = x; i; i -= ( i & ( -i ) ) )
            for( int j = y; j; j -= ( j & ( -j ) ) )
                ans += f[i][j];
        return ans;
    }
} t1;

int query( int x1, int y1, int x2, int y2 ){ return t1.find( x2, y2 ) - t1.find( x1 - 1, y2 ) - t1.find( x2, y1 - 1 ) + t1.find( x1 - 1, y1 - 1 ); }

int tmp[N * N];

void solve( int l, int r, int L, int R ){
//  printf( "!%d %d %d %d\n", l, r, L, R );
    if( l > r ) return ;
    if( L == R ){
        for( int i = l; i <= r; ++i ) ask[i].ans = tmp[L];
        return ;
    }
    int mid = ( L + R ) >> 1;
    for( int i = l; i <= r; ++i ){
        if( ask[i].type == 1 && ask[i].k <= mid ) t1.add( ask[i].x1, ask[i].y1, 1 );
    }
    int cntl = 0, cntr = 0;
    for( int i = l; i <= r; ++i ){
        if( !ask[i].type )
            if( ask[i].k <= query( ask[i].x1, ask[i].y1, ask[i].x2, ask[i].y2 ) ){
                ask2[++cntl] = ask[i];
            }
            else{
                ask3[++cntr] = ask[i];
                ask3[cntr].k -= query( ask[i].x1, ask[i].y1, ask[i].x2, ask[i].y2 );
            }
        else
            if( ask[i].k <= mid ) ask2[++cntl] = ask[i];
            else ask3[++cntr] = ask[i];
    }
    for( int i = 1; i <= cntl; ++i ){ ask[l + i - 1] = ask2[i]; if( ask2[i].type ) t1.add( ask2[i].x1, ask2[i].y1, -1 ); }
    for( int i = 1; i <= cntr; ++i ){ ask[l + cntl + i - 1] = ask3[i]; if( ask3[i].type ) t1.add( ask3[i].x1, ask3[i].y1, -1 ); }
    solve( l, l + cntl - 1, L, mid );
    solve( l + cntl, r, mid + 1, R );
}

bool cmp( node x, node y ){
    if( x.type == y.type ) return x.id < y.id;
    return x.type < y.type;
}

int main(){
    scanf( "%d%d", &n, &q );
    for( int i = 1; i <= n; ++i ) for( int j = 1; j <= n; ++j ){ ask[++cnt].x1 = i, ask[cnt].y1 = j, ask[cnt].type = 1; scanf( "%d", &ask[cnt].k ); tmp[cnt] = ask[cnt].k; }
    sort( tmp + 1, tmp + cnt + 1 );
    int _n = unique( tmp + 1, tmp + cnt + 1 ) - tmp - 1;
    for( int i = 1; i <= cnt; ++i ) ask[i].k = lower_bound( tmp + 1, tmp + _n + 1, ask[i].k ) - tmp;
    for( int i = 1; i <= q; ++i ){
        ask[++cnt].type = 0;
        scanf( "%d%d%d%d%d", &ask[cnt].x1, &ask[cnt].y1, &ask[cnt].x2, &ask[cnt].y2, &ask[cnt].k );
        ask[cnt].id = i;
    }
    solve( 1, cnt, 0, 1e6 );
    sort( ask + 1, ask + cnt + 1, cmp );
    for( int i = 1; i <= q; ++i ) printf( "%d\n", ask[i].ans );
    return 0;
}