首先，构造上下界。上界显然是 $nm-1$，下界需要分奇偶讨论。右下左上联通，所以需要至少 $n-1+m-1$ 的长度，我们发现对于 $m,n$ 中有一个奇数的情况是可以满足的。在奇数那里从中间一列劈开，然后分别向两边连。对于偶数，我们无法到最中间的那个，那么只能选择相对更靠中间的那个。然后如果我们链延生选择同侧，就是这样

会造成长度加一，也就是 $n+m-1$。

最后的构造很显然就是调整法了。我们逐步将最小情况往大去调整，直到遇到答案。以 $n$ 为奇数为例，我们先构造出红笔的主链，然后目前潜在的连边方式是黑笔的下界，如果我们要调整就一点一点地调整成蓝笔的上界，按照那个螺旋线一点点走就行。

我们可以设置一个标号数组，$f_{i,j}$ 表示该点连边的朝向，初始化就初始黑边朝向即可。然后如果要变更，就改成蓝笔朝向。

本题在 $n,m$ 为偶数的时候的构造，初始状态不要设置为图 $1$ 中那种最小值情况，而是同理设置为图 $2$，方便后续调整构造，图 $1$ 形态不方便调整。

代码细节很多，还有些分类讨论，不太好写。从上午调到下午，WA了很多发，中间还换了种实现方式，终于写出了一个较为简洁的正解。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int n,m,k,f[maxn][maxn]; bool flip=0;
bool vis[maxn][maxn];
void add(int x1,int y1,int x2,int y2){
	if(flip) swap(x1,y1),swap(x2,y2);
	cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
}
void merge1(int l,int r,int row){ for(int i=l;i<r;i++) add(i,row,i+1,row); }
void merge2(int l,int r,int line){ for(int i=l;i<r;i++) add(line,i,line,i+1); }
void merge3(int x,int y){
	if(f[x][y]==1) add(x,y,x-1,y);
	if(f[x][y]==2) add(x,y,x,y+1);
	if(f[x][y]==3) add(x,y,x+1,y);
	if(f[x][y]==4) add(x,y,x,y-1);
}
int dy,nx,ny,ns,p;
bool check1(){
	if(nx+1==p&&((ny==m&&ns==2)||(ny==2&&ns==4))) return 0;
	return 1;
}
bool check2(){
	if(nx-1==p&&((ny==1&&ns==4)||(ny==m-1&&ns==2))) return 0;
	return 1;
}
int main(){
	cin>>n>>m>>k;
	if(m%2==1) swap(n,m),flip^=1;
	if(n%2==1&&(k<n+m-2||k>=n*m)){ cout<<"NIE"<<endl; return 0; }
	if(n%2==0&&(k<n+m-1||k>=n*m)){ cout<<"NIE"<<endl; return 0; }
	if(n==2) swap(n,m),flip^=1;
	cout<<"TAK"<<endl; k-=n+m-2; p=(n+1)/2;
	merge1(1,p,1); merge2(1,m,p); merge1(p,n,m);
	memset(f,0,sizeof(f)); memset(vis,1,sizeof(vis));
	for(int i=1;i<p;i++)
		for(int j=2;j<=m;j++) f[i][j]=3,vis[i][j]=0;
	for(int i=p+1;i<=n;i++)
		for(int j=1;j<m;j++) f[i][j]=1,vis[i][j]=0;
	dy=1,nx=1,ny=1,ns=2;
	while(k&&nx!=p&&check1()){
		if(!vis[nx][ny+dy]){ f[nx][ny]=ns; ny+=dy; k--; }
		else if(ny==m){ f[nx][ny]=3; nx++; ns=4; dy=-1; k--; }
		else if(ny==2){ f[nx][ny]=3; nx++; ns=2; dy=1; k--;  }
		f[nx][ny]=0;
	}
	dy=-1,nx=n,ny=m,ns=4;
	while(k&&check2()){
		if(!vis[nx][ny+dy]){ f[nx][ny]=ns; ny+=dy; k--; }
		else if(ny==1){ f[nx][ny]=1; nx--; ns=2; dy=1; k--; }
		else if(ny==m-1){ f[nx][ny]=1; nx--; ns=4; dy=-1; k--;  }
		f[nx][ny]=0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) merge3(i,j);
	return 0;
}