SPOJ: FREQUENT – Frequent values

Problem Link : http://www.spoj.com/problems/FREQUENT/

Solution Idea:

    In this problem an array of non-decreasing order is given. In each query a range l and r is given. You have to tell the maximum frequency of a number in the range l to r.

    Now as the given array is in non-decreasing order. So you can replace array a = {1 1 1 2 2 3 3 3 3} by another array b = {3 2 4}. After this compression the problem is converted to a Range Maximum query problem which can be easily solved by segment tree or sparse table. Now for each query determine the index in the compress array and perform range maximum query on that range.

    Think about the first and index of the query range. You need to handle them separately.



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005

pii block[mx];

int dp[mx][20];

int ara[mx],id[mx],cnt=0,table[mx];

int func(int idx, int p)
{
    if(idx>cnt) return 0;
    if(p==0)
    {
        return dp[idx][p]=table[idx];
    }
    int &ret=dp[idx][p];
    if(ret!=-1) return ret;
    ret=max(func(idx,p-1),func(idx+(1<<(p-1)),p-1));
    return ret;
}

int query(int l, int r)
{
    if(r<l) return 0;
    if(l==r) return table[l];
    int log=(int)log2(r-l);
    return max(func(l,log),func(r-(1<<log)+1,log));
}

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n,q;
    while(sf(n))
    {
        if(n==0) break;
        sf(q);
        for(int i=1; i<=n; i++)
        {
            sf(ara[i]);
        }
        cnt=0;
        ms(table,0);
        ms(dp,-1);
//        ms(block,0);
//        ms(id,0);
        for(int i=1; i<=n; i++)
        {
            int j=i;
            cnt++;
            block[cnt].ff=i;
            while(ara[j]==ara[i] && j<=n)
            {
                id[j]=cnt;
                table[cnt]++;
                j++;
            }
            j--;
            block[cnt].ss=j;
            i=j;
        }

        while(q--)
        {
            int a,b;
            sff(a,b);
            if(id[a]==id[b])
            {
                printf("%d\n",b-a+1);
            }
            else
            {
                int l=id[a];
                int r=id[b];
                int ans=0;
                ans=max(ans,block[l].ss-a+1);
                l++;
                ans=max(ans,b-block[r].ff+1);
                r--;
                ans=max(ans,query(l,r));
                printf("%d\n",ans);
            }
        }

    }

    return 0;
}

Advertisements

Light OJ: 1162 – Min Max Roads

Problem Link : http://lightoj.com:81/volume/problem/1162


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005

int n,q;
vector<int>g[mx],cost[mx];

int par[mx], dis[mx], level[mx];

int sparse_par[mx][20],sparse_max[mx][20], sparse_min[mx][20];

void dfs(int u, int cnt, int from)
{
    par[u]=from;
    level[u]=cnt;

    for(int i=0;i<SZ(g[u]);i++)
    {
        int v=g[u][i];
        if(v!=from)
        {
            dis[v]=cost[u][i];
            dfs(v,cnt+1,u);
        }
    }
}

void build_table()
{
    ms(sparse_par,-1);

    sparse_par[1][0]=par[1];
    sparse_min[1][0]=INT_MAX;
    sparse_max[1][0]=0;

    for(int i=2;i<=n;i++)
    {
        sparse_par[i][0]=par[i];
        sparse_min[i][0]=dis[i];
        sparse_max[i][0]=dis[i];
    }

    for(int j=1;1<<j<n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(sparse_par[i][j-1]!=-1)
            {
//                D(i);
//                D(j);

                sparse_par[i][j]=sparse_par[sparse_par[i][j-1]][j-1];
                sparse_max[i][j]=max(sparse_max[i][j-1],sparse_max[sparse_par[i][j-1]][j-1]);
                sparse_min[i][j]=min(sparse_min[i][j-1],sparse_min[sparse_par[i][j-1]][j-1]);
//                D(sparse_par[i][j]);
//                D(sparse_max[i][j]);
//                D(sparse_min[i][j]);
            }
        }
    }

}

pii query(int p, int q)
{
    if(level[p]<level[q]) swap(p,q);

    int log=log2(level[p]);

    int maxi=0,mini=INT_MAX;

    for(int i=log;i>=0;i--)
    {
        if(level[p]-(1<<i)>=level[q])
        {
            maxi=max(maxi,sparse_max[p][i]);
            mini=min(mini,sparse_min[p][i]);

            p=sparse_par[p][i];

        }
    }

    if(p==q)
    {
        return pii(mini,maxi);
    }

    for(int i=log;i>=0;i--)
    {
        if(sparse_par[p][i]!=-1 && sparse_par[p][i]!=sparse_par[q][i])
        {
            maxi=max(maxi,max(sparse_max[p][i],sparse_max[q][i]));
            mini=min(mini,min(sparse_min[p][i],sparse_min[q][i]));
            p=sparse_par[p][i];
            q=sparse_par[q][i];
        }
    }

    maxi=max(maxi,max(dis[p],dis[q]));
    mini=min(mini,min(dis[p],dis[q]));

    return pii(mini,maxi);


}

int main()
{

//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        sf(n);

        for(int i=1;i<n;i++)
        {
            int a,b,c;
            sfff(a,b,c);
            g[a].pb(b);
            g[b].pb(a);
            cost[a].pb(c);
            cost[b].pb(c);
        }

        dis[1]=0;
        dfs(1,0,1);

        build_table();

        sf(q);

        PRINT_CASE;

        while(q--)
        {
            int a,b;
            sff(a,b);
            pii ans=query(a,b);
            printf("%d %d\n",ans.ff,ans.ss);

        }

        for(int i=0;i<=n;i++)
        {
            g[i].clear();
            cost[i].clear();
        }


    }

    return 0;
}


Light OJ: 1128 – Greatest Parent

Problem Link : http://lightoj.com:81/volume/problem/1128


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n,q;

int par[100005];
ll dis[100005];

int sparse_par[100005][20];


void build_talbe()
{
    ms(sparse_par,-1);
    for(int i=0; i<n; i++)
    {
        sparse_par[i][0]=par[i];
    }

    for(int j=1; 1<<j <n; j++)
    {
        for(int i=0; i<n; i++)
        {
            sparse_par[i][j]=sparse_par[sparse_par[i][j-1]][j-1];
        }
    }
}

ll query(int p, ll v)
{

    int log=log2(n);

    for(int i=log; i>=0; i--)
    {

//        int a=sparse_par[p][i];
//        int b=dis[sparse_par[p][i]];

        if(dis[sparse_par[p][i]]>=v)
        {
            p=sparse_par[p][i];
        }
    }

    return p;

}

int main()
{

//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    sf(t);

    TEST_CASE(t)
    {
        sff(n,q);

        par[0]=0;
        dis[0]=1;

        loop1(i,n-1)
        {
            ll a,b;
            sffl(a,b);
            par[i]=a;
            dis[i]=b;
        }


        build_talbe();

        PRINT_CASE;

        while(q--)
        {
            ll a,b;
            sffl(a,b);
            printf("%d\n",query(a,b));
        }


    }

    return 0;
}


Light OJ: 1101 – A Secret Mission

Problem Link : http://lightoj.com:81/volume/problem/1101


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

typedef pair<int,pii > piii;

vector< piii > g1;

vector<int>g[50005],cost[50005];

int n,m;

int par[50004];

int find_par(int u)
{
    return par[u]=(par[u]==u)?u:find_par(par[u]);
}


int dis[50005],level[50005];

void dfs(int u, int cnt, int from)
{
    level[u]=cnt;
    par[u]=from;

    for(int i=0; i<SZ(g[u]); i++)
    {
        int v=g[u][i];

        if(level[v]==-1)
        {
            dis[v]=cost[u][i];
            dfs(v,cnt+1,u);
        }
    }

}

int sparse_par[50005][16];
int sparse_max[50005][16];

void build_table()
{

    ms(sparse_par,-1);

    for(int i=1; i<=n; i++)
        sparse_par[i][0]=par[i],sparse_max[i][0]=dis[i];

    for(int i=1; 1<<i <=n; i++)
    {
        for(int j=1; j<=n; j++)
            if(sparse_par[j][i-1]!=-1)
            {
                sparse_par[j][i]=sparse_par[sparse_par[j][i-1]][i-1];
                sparse_max[j][i]=max(sparse_max[j][i-1],sparse_max[sparse_par[j][i-1]][i-1]);
            }
    }


}

int query(int p, int q)
{
    int a=p,b=q;

    if(level[p]<level[q]) swap(p,q);

    int log=log2(level[p]);

    int ret=0;

    for(int i=log; i>=0; i--)
    {
        if(level[p]-(1<<i) >=level[q])
        {
            ret=max(ret,sparse_max[p][i]);
            p=sparse_par[p][i];
        }
    }

    if(p==q) return ret;

    for(int i=log; i>=0; i--)
        if(sparse_par[p][i]!=-1 && sparse_par[p][i]!=sparse_par[q][i])
        {
            ret=max(ret,max(sparse_max[p][i],sparse_max[q][i]));
            p=sparse_par[p][i],q=sparse_par[q][i];
        }
    ret=max(ret,max(dis[p],dis[q]));
    return ret;

}

int main()
{

    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);



    int t;
    sf(t);
    TEST_CASE(t)
    {

        g1.clear();

        sff(n,m);
        for(int i=0; i<m; i++)
        {
            int a,b,c;
            sfff(a,b,c);
            g1.pb(piii(c,pii(a,b)));
        }

        sort(all(g1));

//        reverse(all(g1));

        int cnt=0;

        for(int i=1; i<=n; i++) par[i]=i,g[i].clear(),cost[i].clear();

        for(int i=0; i<SZ(g1) && cnt<n-1; i++)
        {
            int a=g1[i].ss.ff;
            int b=g1[i].ss.ss;
            int c=g1[i].ff;
            int u=find_par(a);
            int v=find_par(b);

            if(u!=v)
            {
                par[v]=u;
                g[a].pb(b);
                g[b].pb(a);
                cost[a].pb(g1[i].ff);
                cost[b].pb(g1[i].ff);
                cnt++;
            }
        }


        ms(level,-1);
        dis[1]=0;

        dfs(1,0,1);

        build_table();

        int q;
        sf(q);
        PRINT_CASE;

        while(q--)
        {
            int a, b;
            sff(a,b);
            printf("%d\n",query(a,b));
        }



    }

    return 0;
}


Light OJ: 1081 – Square Queries

Problem Link : http://lightoj.com:81/volume/problem/1081

Solution Idea: Build a 2D sparse table for the given array. Then query the answer form the sparse table.


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n,q;

int ara[505][505];
int sparse[505][505][16];

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

int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        sff(n,q);

        loop(i,n) loop(j,n) sf(ara[i][j]);

        build();

        PRINT_CASE;

        while(q--)
        {
            int i,j,s;
            sfff(i,j,s);
            int k=log2(s);
            int a=1<<k;
            i--;
            j--;
            int ans=max(max(sparse[i][j][k],sparse[i+s-a][j][k]),max(sparse[i][j+s-a][k],sparse[i+s-a][j+s-a][k]));
            pf("%d\n",ans);

        }

    }

    return 0;
}