#include #include #include #include using namespace std; vector >tr(const vector >&A) { assert(!A.empty()&&!A[0].empty()); int H=A.size(),W=A[0].size(); vector >ret(W,vector(H)); for(int i=0;i > >solveC(int H,int W) { if(H<3||W<3)return{-1,{}}; if(H%2==0) { int K=0; vector >ret; if(H%4==0) { if(H>4) { auto p=solveC(H-4,W); K=p.first; ret=p.second; } assert(ret.size()==H-4); ret.push_back(vector(W,K+1));//H-4 ret.push_back(vector(W,K+2));//H-3 ret.push_back(vector(W,K+1));//H-2 ret.push_back(vector(W,K+2));//H-1 ret[H-3][0]=K+1; ret[H-2][W-1]=K+2; K+=2; } else { if(H>6) { auto p=solveC(H-6,W); K=p.first; ret=p.second; } assert(ret.size()==H-6); ret.push_back(vector(W,K+1));//H-6 ret.push_back(vector(W,K+2));//H-5 ret.push_back(vector(W,K+1));//H-4 ret.push_back(vector(W,K+3));//H-3 ret.push_back(vector(W,K+2));//H-2 ret.push_back(vector(W,K+3));//H-1 ret[H-5][0]=K+1; ret[H-2][0]=K+3; ret[H-3][W-1]=K+2; ret[H-4][W-1]=K+2; K+=3; } return{K,ret}; } if(W%2==0) { auto p=solveC(W,H); p.second=tr(p.second); return p; } assert(H%2==1&&W%2==1); if(min(H,W)==3)return{-1,{}}; auto p=solveC(H-2,W-1); int K=p.first; auto ret=p.second; for(int i=0;i(W,K+1)); ret.push_back(vector(W,K+1)); K++; return{K,ret}; } pair > >solveT(int H,int W) { if(H>W) { auto p=solveT(W,H); if(p.first>0)p.second=tr(p.second); return p; } assert(H<=W); if(H==2)return{-1,{}}; else if(H==3) { if(W<6)return{-1,{}}; else { int K=4; vector >ret; ret.push_back({1,2,2,2,2}); ret.push_back({1,1,2,3,4}); ret.push_back({1,3,3,3,3}); for(int i=0;i >ret; ret.push_back({1,2}); ret.push_back({1,1}); ret.push_back({1,3}); ret.push_back({3,3}); for(int i=0;i >ret; ret.push_back({1,1,1}); ret.push_back({2,1,4}); ret.push_back({2,2,2}); ret.push_back({2,3,5}); ret.push_back({3,3,3}); for(int i=0;i > >solveCT(int H,int W) { if(H>W) { auto p=solveCT(W,H); if(p.first>0)p.second=tr(p.second); return p; } if(H==2)return{-1,{}}; else if(H==3) { int K=2; vector >ret; ret.push_back(vector(W,1)); ret.push_back(vector(W,2)); ret.push_back(vector(W,1)); ret[0][W-1]=2; ret[2][W-1]=2; ret[1][0]=1; return{K,ret}; } else if(H==4) { int K=3; vector >ret; ret.push_back({1,1}); ret.push_back({2,2}); ret.push_back({2,3}); ret.push_back({2,2}); for(int i=0;i >ret={ {1,1,1,1,1}, {2,1,3,3,3}, {2,2,2,2,3}, {2,4,3,3,3}, {4,4,4,4,4} }; return{K,ret}; } else { auto p=solveT(H-1,W-2); assert(p.first>0); int K=p.first; auto ret=p.second; for(int i=0;i(W,K+1)); K++; return{K,ret}; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); /* for(int H=2;H<=7;H++)for(int W=2;W<=7;W++) { auto p=solveT(H,W); if(p.first==-1)cout<<"NA ("<>H>>W; { auto p=solveC(H,W); if(p.first==-1)cout<<"-1\n"; else { cout<