2d sparse table

//2d sparse table
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int mod = 1e9 + 7;

const int N = 5e5 + 10;

int arr[501][501],table[501][501][40];int n,q;

void init() {
    for(int k = 0;(1<<k)<=n;k++) {
        for(int i = 1;i+(1<<k)-1<=n;i++) {
            for(int j = 1;j+(1<<k)-1<=n;j++) {
                if(k == 0) {
                    table[i][j][k] = arr[i][j];
                }
                else {
                    int a=1<<(k-1);
                    table[i][j][k]=max(max(table[i][j][k-1],table[i+a][j][k-1]),max(table[i][j+a][k-1],table[i+a][j+a][k-1]));
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t;
    scanf("%d",&t);
    int ajinka = 1;
    while(t--) {
        scanf("%d%d",&n,&q);
        memset(table,0,sizeof(table));
        for(int i = 1;i<=n;i++) {
            for(int j = 1;j<=n;j++) {
                scanf("%d",&arr[i][j]);
            }
        }
        init();
        printf("Case %d:\n",ajinka++);
        while(q--) {
            int i,j,s;
            scanf("%d%d%d",&i,&j,&s);
            int k = log2(s);
            int a = (1<<k);
            int ans = max(max(table[i][j][k],table[i+s-a][j][k]),max(table[i][j+s-a][k],table[i+s-a][j+s-a][k]));
            printf("%d\n",ans);
        }
    }

    return 0;
}