1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n,m,Q;
vector <int > a[30005];
int x[30005],y[30005];
int f[5005][5005],g[5005][5005];
bool chk()
{
	for(int i=1;i<=n;i++) for(int j=i;j<=n;j++)
	{
		int c=f[i][j];
		if(i==1) y[j]=c;
		else if(j==n) x[i]=c-y[j];
	} 
	for(int i=1;i<=n;i++) for(int j=i;j<=n;j++)
	{
		int c=f[i][j];
		if(x[i]+y[j]!=c) return 0;
	}
//	for(int i=1;i<=n;i++) a[i][pos]=x[i],a[i][pos+2]=y[i];
//	for(int i=1;i<=n;i++) a[i].erase(a[i].begin()+pos+1);
	return 1;
}
void solve()
{
	cin>>n>>m>>Q;
	for(int i=1;i<=n;i++) a[i].resize(m+1);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
	while(m>2)
	{
		int flg=0;
		for(int l=1;l<=m;l++)
		{
			for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=(i==j?a[i][l]:INF);
			for(int r=l+1;r<=m;r++)
			{
				for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=INF;
				for(int i=1;i<=n;i++) for(int j=i,mn=INF;j<=n;j++) mn=min(mn,f[i][j]),g[i][j]=mn+a[j][r];
				for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=g[i][j];
				if(r-l+1>=3&&chk())
				{
//					cerr<<"... "<<l<<" "<<r<<"\n";
					for(int i=1;i<=n;i++) a[i][l]=x[i],a[i][r]=y[i];
					for(int i=1;i<=n;i++) for(int j=0;j<r-l-1;j++) a[i].erase(a[i].begin()+l+1);
					m-=r-l-1;
					flg=1;
					break;
				}
			}
			if(flg) break;
		}
		if(!flg) break;
	}
	if(!Q) cout<<m<<"\n";
	else
	{
		cout<<m<<"\n";
		for(int i=1;i<=n;i++) 
		{
			for(int j=1;j<=m;j++) cout<<a[i][j]<<" ";
			cout<<"\n";
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}