#include "gmp.h"
#include"gmp-impl.h"
#include"mp.h"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define MAXM		100
#define MAXN		100

#define eps		0.001

int m,n,a[MAXM+2][MAXN+2],sol[MAXM+2][MAXN+2],valfin;
mpf_t rez[MAXN+2],b[MAXN+2],b1[MAXN+2],b2[MAXN+2],y[MAXN+2];
mpf_t row1[MAXN+2][MAXN+2],row2[MAXN+2][MAXN+2];

int isinteger(mpf_t x)
{
	double y=mpf_get_d(x);

	y=fabs((double)(y-(int)y));
	if(y<eps||1-y<eps)
		return 1;
	return 0;
}

int integer(mpf_t x)
{
	double y=mpf_get_d(x);

	if(y>0)
		return (int)(y+0.5);
	else
		return (int)(y-0.5);
}

int LUPdesc(mpf_t a[MAXN+2][MAXN+2],int pi[MAXN+2],int n)
//returneaza rangul matricei caracteristice
{
	int i,j,k,r;
	mpf_t p,tt;
	double ttt;

	printf("Calculez descompunerea matricii sistemului...te rog asteapta O(n^3)\n\n");

	for(i=1;i<=n;i++)
		pi[i]=i;
	mpf_init(p),mpf_init(tt);
	for(k=1;k<=n;k++)
	{
		mpf_set_si(p,0);
		for(i=k;i<=n;i++)
		{
			mpf_set(tt,a[i][k]);
			mpf_abs(tt,tt);
			if(mpf_cmp(tt,p)>0)
			{
				mpf_set(p,tt);
				r=i;
			}
		}
		ttt=mpf_get_d(p);
		if(ttt<0.000001)
		{
			mpf_clear(p),mpf_clear(tt);
			return k-1;
			//Matrice singulara
			//presupunem ca avem sistem nedeterminat
		}
		j=pi[k]; pi[k]=pi[r]; pi[r]=j;
		for(i=1;i<=n;i++)
		{
			mpf_set(p,a[k][i]);
			mpf_set(a[k][i],a[r][i]);
			mpf_set(a[r][i],p);
		}
		for(i=k+1;i<=n;i++)
		{
			mpf_div(a[i][k],a[i][k],a[k][k]);
			for(j=k+1;j<=n;j++)
			{
				mpf_mul(tt,a[i][k],a[k][j]);
				mpf_sub(a[i][j],a[i][j],tt);
			}
		}
	}
	mpf_clear(p),mpf_clear(tt);
	return n;
}

int LUPsol(mpf_t a[MAXN+2][MAXN+2],mpf_t b[MAXN+2],int pi[MAXN+2],int n,mpf_t x[MAXN+2])
//intoarce 0 daca apar numere fractionare
//intoarce 1 daca este OK
{
	int i,j;
	mpf_t suma,tt;

	mpf_init(suma),mpf_init(tt);

	for(i=1;i<=n;i++)
	{
		mpf_set_si(suma,0);
		for(j=1;j<i;j++)
		{
			mpf_mul(tt,a[i][j],y[j]);
			mpf_add(suma,suma,tt);
			//suma+=a[i][j]*y[j];
		}
		mpf_sub(y[i],b[pi[i]],suma);
		//y[i]=b[pi[i]]-suma;
	}
	for(i=n;i>=1;i--)
	{
		mpf_set_si(suma,0);
		for(j=i+1;j<=n;j++)
		{
			mpf_mul(tt,a[i][j],x[j]);
			mpf_add(suma,suma,tt);
			//suma+=a[i][j]*x[j];
		}
		mpf_sub(tt,y[i],suma);
		mpf_div(x[i],tt,a[i][i]);
		//x[i]=(y[i]-suma)/a[i][i];
		if(!isinteger(x[i]))
		{
			mpf_clear(suma),mpf_clear(tt);

			return 0;
		}
	}
	mpf_clear(suma),mpf_clear(tt);

	return 1;
}

void read()
{
	long i,j;
	FILE *fi=fopen("rubik.in","rt");

	fscanf(fi,"%d%d",&m,&n);
	memset(a,0,sizeof(a));
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			fscanf(fi,"%d",&(a[i][j]));

	fclose(fi);
}

void solve()
{
	int i,j,k,nn;
	int pi[MAXN+2];
	mpf_t tt;

	//calculeaza prima linie a solutiei
	//sistem de n ec. cu n necunoscute
	//care sunt cant. care se adauga la celulele de sus
	//sistemul este: [A][x]=[b], unde [A]=row2,[b]=b si [x]=rez
	//in prima faza, calculam [P][A]=[L][U]
	printf("Aloc numerele...ai rabdare te rog...\n\n");
	//alocate numbers
	mpf_init(tt);
	for(i=0;i<=n+1;i++)
		for(j=0;j<=n+1;j++)
			mpf_init(row1[i][j]),mpf_init(row2[i][j]);
	for(i=0;i<=n+1;i++)
		mpf_init(b1[i]),mpf_init(b2[i]),mpf_init(b[i]),mpf_init(rez[i]);
	for(i=0;i<=n+1;i++)
		mpf_init(y[i]);


	for(i=1;i<=n;i++)
		mpf_set_si(row2[i][i],1);
	for(k=2;k<=m+1;k++)
	{
		for(j=1;j<=n;j++)
			for(i=1;i<=n;i++)
			{
				mpf_add(row1[j][i],row2[j-1][i],row1[j][i]);
				mpf_add(row1[j][i],row2[j][i],row1[j][i]);
				mpf_add(row1[j][i],row2[j+1][i],row1[j][i]);
				mpf_neg(row1[j][i],row1[j][i]);
				//row1[j][i]=-row1[j][i]-row2[j-1][i]-row2[j][i]-row2[j+1][i];
			}

		//schimba randurile intre ele
		for(i=0;i<=n+1;i++)
			for(j=0;j<=n+1;j++)
			{
				mpf_set(tt,row2[i][j]);
				mpf_set(row2[i][j],row1[i][j]);
				mpf_set(row1[i][j],tt);
			}
	}
	nn=LUPdesc(row2,pi,n);

	//acum, pt. valfin de la 0 la 1000 incercam sa obtinem un sistem
	//cu rezultate intregi
	for(valfin=0;valfin<=1000;valfin++)
	{
		for(i=0;i<=n+1;i++)
			mpf_set_si(b1[i],0),mpf_set_si(b2[i],0);
		for(k=2;k<=m+1;k++)
		{
			for(j=1;j<=n;j++)
			{
				mpf_set_si(tt,valfin);
				mpf_sub(tt,tt,b1[j]);
				mpf_sub(tt,tt,b2[j-1]);
				mpf_sub(tt,tt,b2[j]);
				mpf_sub(tt,tt,b2[j+1]);
				mpf_sub_ui(tt,tt,a[k-1][j]);
				mpf_set(b1[j],tt);
				//b1[j]=valfin-b1[j]-b2[j-1]-b2[j]-b2[j+1]-a[k-1][j];
			}

			//schimba randurile intre ele
			for(i=0;i<=n+1;i++)
			{
				mpf_set(tt,b1[i]);
				mpf_set(b1[i],b2[i]);
				mpf_set(b2[i],tt);
			}
		}
		for(i=0;i<=n+1;i++)
			mpf_set(b[i],b2[i]);
		for(i=1;i<=n;i++)
			mpf_neg(b[i],b[i]);
		if(LUPsol(row2,b,pi,nn,rez))
			break;

		//printf("Mai am memorie %ld\n",coreleft());
		printf("Pt. valoarea finala = %d nu se poate...\n\n",valfin);
	}
	assert(valfin!=1001);

	for(i=1;i<=nn;i++){
		printf("rez[%d]= ",i); mpf_dump(rez[i]); printf("");}

	//calculeaza toata matricea
	//matricea solutiei o construim in sol
	memset(sol,0,sizeof(sol));
	for(i=1;i<=nn;i++)
		sol[1][i]=integer(rez[i]);
	for(;i<=n;i++)
		sol[1][i]=0; //valoare arbitrara

	for(i=2;i<=m;i++)
		for(j=1;j<=n;j++)
			sol[i][j]=valfin-a[i-1][j]-sol[i-2][j]-sol[i-1][j-1]-sol[i-1][j]-sol[i-1][j+1];

	//let's free the space
	mpf_clear(tt);
	for(i=0;i<=n+1;i++)
		for(j=0;j<=n+1;j++)
			mpf_clear(row1[i][j]),mpf_clear(row2[i][j]);
	for(i=0;i<=n+1;i++)
		mpf_clear(b1[i]),mpf_clear(b2[i]),mpf_clear(b[i]),mpf_clear(rez[i]);
	for(i=0;i<=n+1;i++)
		mpf_clear(y[i]);

}

void write()
{
	FILE *fo=fopen("rubik.out","wt");
	int i,j,nmoves=0,k;

	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(sol[i][j]!=0)
				nmoves++;
	fprintf(fo,"%d\n%d\n",valfin,nmoves);
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(sol[i][j]!=0)
				fprintf(fo,"%d %d %d\n",i,j,sol[i][j]);

	fclose(fo);
}

void main()
{
	mpf_set_default_prec(256);

	//printf("Mai am memorie %ld\n",coreleft());
	//printf("Sizeof(mpf_t) is %d\n",sizeof(mpf_t));
	read();
	solve();
	write();


	//printf("Mai am memorie %ld\n",coreleft());
}