#include <cstdio>
#include <cstring>
#include <string>
#include <fstream>

const int MAXN = 520;
const int LOGMAXN = 15;
const int dim = 8192;
using namespace std;

int dp[MAXN][MAXN][LOGMAXN], x, y, L;
int lg[MAXN], pw[MAXN], logn, i, p, pwL, logL, ans, stp;
int n, m, k, j;
char ax[dim];
int pz;

void cit (int &x)
{
	x = 0;

	while (ax[pz] < '0' || ax[pz] > '9')
		if (++pz == dim)
			fread (ax, 1, dim, stdin),pz = 0;

	while (ax[pz] >= '0' && ax[pz] <= '9')
	{
		 x = x * 10 + ax[pz] - '0';
		 if (++pz == dim)
			 fread (ax, 1, dim, stdin),pz =0;
	}

}
int main ()
{	
	
	freopen ("plantatie.in", "r", stdin);
	freopen ("plantatie.out", "w", stdout);
	cit (n);
       	cit (m);

	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++) 
			cit (dp[i][j][0]);

	pw[0] = 1; pw[1] = 2; 
	for (i = 2; i <= n; i++) 
	{
		lg[i] = lg[i >> 1] + 1;
	  	pw[i] = pw[i - 1] << 1;
	}
	logn = lg[n];	

	for (k = 1; k <= logn; k++)
	{
		p = pw [k - 1];
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				if (i + p <= n && j + p <= n)
					dp[i][j][k] = max (dp[i][j][k - 1], max (dp[i + p][j][k - 1], max (dp[i][j + p][k - 1], dp[i + p][j + p][k - 1])));
	}

	for (stp = 1; stp <= m; ++stp)
	{
		cit (x); cit (y); cit (L);
		logL = lg[L];
		pwL = pw[logL];
#ifdef DEBUG
		printf ("%d %d %d\n", x, y, L);
		printf ("%d %d %d %d %d %d\n", x, y, x + L - pwL, y + L - pwL, logL, pwL);
		printf ("\n");
#endif
		ans = max(dp[x][y][logL], max (dp[x][y + L - pwL][logL], max (dp[x + L - pwL][y][logL], dp[x + L - pwL][y + L - pwL][logL])));
		printf ("%d\n", ans);
	}
	return 0;
}