#include using namespace std; #define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__) #define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__) #define OVERLOAD_REP(_1, _2, _3, _4, name, ...) name #define REP1(n) for(ll i=0;i<(n);i++) #define REP2(i, n) for (ll i=0;i<(n);i++) #define REP3(i, a, n) for (ll i=a;i<(n);i++) #define REP4(i, a, b, n) for(ll i=a;i<(n);i+=b) #define rep(...) OVERLOAD_REP(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define OVERLOAD_RREP(_1, _2, _3, _4, name, ...) name #define RREP1(n) for(ll i=(n)-1;i>=0;i--) #define RREP2(i, n) for(ll i=(n)-1;i>=0;i--) #define RREP3(i, a, n) for(ll i=(n)-1;i>=(a);i--) #define RREP4(i, a, b, n) for(ll i=(n)-1;i>=(a);i-=(b)) #define rrep(...) OVERLOAD_RREP(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__) #define uniq(a) sort(all(a));a.erase(unique(all(a)),end(a)) #define len(n) (long long)(n).size() using ll = long long; using ld = long double; using ull = unsigned long long; using vi = vector; using vvi = vector; using vvvi = vector; using vll = vector; using vvll = vector; using vvvll = vector; using vs = vector; using vvs = vector; using vvvs = vector; using vld = vector; using vvld = vector; using vvvld = vector; using vc = vector; using vvc = vector; using vvvc = vector; using pll = pair; using vpll = vector; using vvpll = vector; ll intpow(ll a,ll b){ ll ans = 1; while (b){ if (b & 1){ ans *= a; } a *= a; b /= 2; } return ans; } ll modpow(ll a,ll b,ll c){ ll ans = 1; while (b){ if (b & 1){ ans *= a; ans %= c; } a *= a; a %= c; b /= 2; } return ans; } template inline T floor(T a, T b) { T q = a / b; T r = a % b; if (r != 0 && ((r < 0) != (b < 0))) q--; return q; } template inline T ceil(T a, T b) { T q = a / b; T r = a % b; if (r != 0 && ((r < 0) == (b < 0))) q++; return q; } template inline T bmod(T a, T b) { T r = a % b; if (r < 0) r += std::abs(b); return r; } template vector>> group_by_first(vector> vec) { sort(vec.begin(), vec.end(), [](auto& a, auto& b) { if (a.first != b.first) return a.first < b.first; return a.second < b.second; }); vector>> res; for (auto& p : vec) { if (res.empty() || res.back().back().first != p.first) { res.push_back({}); } res.back().push_back(p); } return res; } template void input(T&... a){ (cin >> ... >> a); } #define INT(...) int __VA_ARGS__; input(__VA_ARGS__) #define LL(...) ll __VA_ARGS__; input(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__; input(__VA_ARGS__) #define LD(...) ld __VA_ARGS__; input(__VA_ARGS__) #define STR(...) string __VA_ARGS__; input(__VA_ARGS__) #define CHA(...) char __VA_ARGS__; input(__VA_ARGS__) #define VLL(name,length) vll name(length);rep(i,length){cin >> name[i];} #define VVLL(name,h,w) vvll name(h,vll(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVLL(name,a,b,c) vvvll name(a,vvll(b,vll(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VI(name,length) vi name(length);rep(i,length){cin >> name[i];} #define VVI(name,h,w) vvi name(h,vi(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVI(name,a,b,c) vvvi name(a,vvll(b,vi(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VLD(name,length) vld name(length);rep(i,length){cin >> name[i];} #define VVLD(name,h,w) vvld name(h,vld(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVLD(name,a,b,c) vvvld name(a,vvld(b,vld(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VC(name,length) vc name(length);rep(i,length){cin >> name[i];} #define VVC(name,h,w) vvc name(h,vc(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVC(name,a,b,c) vvvc name(a,vvc(b,vc(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VS(name,length) vs name(length);rep(i,length){cin >> name[i];} #define VVS(name,h,w) vvs name(h,vs(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVS(name,a,b,c) vvvs name(a,vvs(b,vs(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define PLL(name) pll name;cin>>name.first>>name.second; #define VPLL(name,length) vpll name(length);rep(i,length){cin>>name[i].first>>name[i].second;} void print(){cout << "\n";} template std::ostream& operator<<(std::ostream& os, const std::pair& p) { os << "(" << p.first << ", " << p.second << ")"; return os; } template std::ostream& operator<<(std::ostream& os, const std::vector& vec) { os << "["; for (size_t i = 0; i < vec.size(); ++i) { os << vec[i]; if (i + 1 < vec.size()) os << ", "; } os << "]"; return os; } template std::ostream& operator<<(std::ostream& os, const std::vector>& a) { os << "["; for (size_t j = 0; j < a.size(); ++j) { os << "(" << a[j].first << ", " << a[j].second << ")"; if (j + 1 < a.size()) os << ", "; } os << "]"; return os; } template std::ostream& operator<<(std::ostream& os, const std::vector>>& mat) { os << "["; for (size_t i = 0; i < mat.size(); ++i) { os << "["; for (size_t j = 0; j < mat[i].size(); ++j) { os << "(" << mat[i][j].first << ", " << mat[i][j].second << ")"; if (j + 1 < mat[i].size()) os << ", "; } os << "]"; if (i + 1 < mat.size()) os << ", "; } os << "]"; return os; } template std::ostream& operator<<(std::ostream& os, const std::set& s) { os << "{"; bool first = true; for (const auto& x : s) { if (!first) os << ", "; os << x; first = false; } os << "}"; return os; } template std::ostream& operator<<(std::ostream& os, const std::map& m) { os << "{"; bool first = true; for (const auto& [key, val] : m) { if (!first) os << ", "; os << key << ": " << val; first = false; } os << "}"; return os; } template void print(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';} #ifdef LOCAL void debug() { std::cerr << "\n"; } template void debug(const T& a, const Ts&... b) { std::cerr << a; (std::cerr << ... << (std::cerr << ' ', b)); std::cerr << '\n'; } void debug_space() {} template void debug_space(const T& a, const Ts&... b) { std::cerr << a; (std::cerr << ... << (std::cerr << ' ', b)); } #else #define debug(...) (void)0 #endif void write(){cout << "\n";} template void write(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';} void write(vll x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvll x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vi x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvi x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vvvi x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void write(vld x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvld x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vvvld x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void write(vc x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvc x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vvvc x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void write(vs x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvs x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vvvs x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void write(pll x){cout << x.first << ' ' << x.second << '\n';} void write(vpll x){rep(i,len(x)){cout << x[i].first << ' ' << x[i].second << '\n';}} void write(vvpll x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j].first << ' ' << x[i][j].second;if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} template T sum(const std::vector& v) { return std::accumulate(v.begin(), v.end(), T(0)); } template auto le(const Set &s, const typename Set::value_type &x, const typename Set::value_type &ngval = typename Set::value_type(-1)) { auto it = s.upper_bound(x); if (it == s.begin()) return ngval; return *prev(it); } template auto lt(const Set &s, const typename Set::value_type &x, const typename Set::value_type &ngval = typename Set::value_type(-1)) { auto it = s.lower_bound(x); if (it == s.begin()) return ngval; return *prev(it); } template auto ge(const Set &s, const typename Set::value_type &x, const typename Set::value_type &ngval = typename Set::value_type(-1)) { auto it = s.lower_bound(x); if (it == s.end()) return ngval; return *it; } template auto gt(const Set &s, const typename Set::value_type &x, const typename Set::value_type &ngval = typename Set::value_type(-1)) { auto it = s.upper_bound(x); if (it == s.end()) return ngval; return *it; } template bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; } template bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; } template bool chmin(T& a, const U& b){ if(a > T(b)){ a = b; return 1; } return 0; } template bool chmax(T& a, const U& b){ if(a < T(b)){ a = b; return 1; } return 0; } vvll ct(ll h,ll w){ if(h > w){ auto res2 = ct(w,h); vvll res(h,vll(w,-1)); rep(i,h){ rep(j,w){ res[i][j] = res2[j][i]; } } return res; } vvll res(h,vll(w,-1)); if(h == 2 || w == 2){ return res; } vvll dp(h+1,vll(w+1,0)); rep(i,3,w+1){ if(3 <= h && i <= w)dp[3][i] = 1; } rep(i,4,w+1){ if(4 <= h && i <= w)dp[4][i] = 1; } rep(i,h+1){ rep(j,w+1){ if(i + 1 <= h && j + 2 <= w)dp[i+1][j+2] |= dp[i][j]; if(i + 2 <= h && j + 1 <= w)dp[i+2][j+1] |= dp[i][j]; } } auto f = [&](auto f,ll p,ll q,ll h,ll w,ll x){ if(h == 3){ res[p+0][q+0] = x; res[p+1][q+0] = x; res[p+2][q+0] = x; res[p+0][q+w-1] = x+1; res[p+1][q+w-1] = x+1; res[p+2][q+w-1] = x+1; rep(j,1,w-1){ res[p+0][q+j] = x; res[p+1][q+j] = x+1; res[p+2][q+j] = x; } return; } else if(h == 4){ rep(j,w){ res[p+0][q+j] = x+1; } rep(j,w-1){ res[p+h-1][q+j] = x; } rep(i,1,h){ res[p+i][q+0] = x; res[p+i][q+w-1] = x+2; } rep(j,1,w-2){ res[p+1][q+j] = x; } res[p+1][q+w-2] = x+1; rep(j,1,w){ res[p+2][q+j] = x+2; } return; } else{ rep(i,h){ res[p+i][q+0] = x; } rep(j,w){ res[p+0][q+j] = x; res[p+h-1][q+j] = x; } f(f,p+1,q+1,h-2,w-1,x+1); } }; f(f,0,0,h,w,1); return res; } vvll c(ll h,ll w){ if(h > w){ auto res2 = c(w,h); vvll res(h,vll(w,-1)); rep(i,h){ rep(j,w){ res[i][j] = res2[j][i]; } } return res; } vvll res(h,vll(w,-1)); if(h == 2 || w == 2){ return res; } if(h == 3 && w % 4 != 0){ return res; } auto f = [&](auto f,ll p,ll q,ll h,ll w,ll x){ if(h == 3){ if(w == 0){ return; } res[p+0][q+0] = x; res[p+1][q+0] = x; res[p+2][q+0] = x; res[p+0][q+1] = x; res[p+1][q+1] = x+1; res[p+2][q+1] = x+1; res[p+0][q+2] = x; res[p+1][q+2] = x; res[p+2][q+2] = x+1; res[p+0][q+3] = x+1; res[p+1][q+3] = x+1; res[p+2][q+3] = x+1; f(f,p,q+4,h,w-4,x+2); return; } if(h == 4){ rep(j,w){ res[p+0][q+j] = x+1; res[p+1][q+j] = x; res[p+2][q+j] = x+1; res[p+3][q+j] = x; } res[p+1][q+w-1] = x+1; res[p+2][q+0] = x; return; } if(h % 2 == 1){ rep(j,w){ res[p+0][q+j] = x; } rep(i,h){ res[p+i][q+0] = x; res[p+i][q+w-1] = x; } f(f,p+1,q+1,h-1,w-2,x+1); return; } if(h % 2 == 0){ rep(i,h){ res[p+i][q+0] = x; } rep(j,w){ res[p+0][q+j] = x; res[p+h-1][q+j] = x; } f(f,p+1,q+1,h-2,w-1,x+1); return; } }; f(f,0,0,h,w,1); return res; } vvll t(ll h,ll w){ if(h > w){ auto res2 = t(w,h); vvll res(h,vll(w,-1)); rep(i,h){ rep(j,w){ res[i][j] = res2[j][i]; } } return res; } vvll res(h,vll(w,-1)); if(h == 2 || w == 2){ return res; } if(h == 3 && w <= 5){ return res; } auto f = [&](auto f,ll p,ll q,ll h,ll w,ll x){ if(h == 5 && w == 5){ vvll temp = { {1,2,2,2,2}, {1,1,5,2,3}, {1,4,5,5,3}, {1,4,5,3,3}, {4,4,4,4,3}, }; x--; rep(i,5){ rep(j,5){ res[p+i][q+j] = x + temp[i][j]; } } return; } else if(h == 3){ if(w <= 5){ return; } rep(j,w){ res[p+0][q+j] = x+1; } res[p+0][q+0] = x; res[p+0][q+w-1] = x+3; rep(j,w){ res[p+1][q+j] = x; } res[p+1][q+w-1] = x+3; res[p+1][q+w-2] = x+3; res[p+1][q+w-3] = x+2; res[p+1][q+w-4] = x+1; rep(j,w){ res[p+2][q+j] = x+2; } res[p+2][q+0] = x; res[p+2][q+w-1] = x+3; return; } else if(h == 4){ rep(j,w){ res[p+0][q+j] = x+2; res[p+1][q+j] = x; res[p+2][q+j] = x+3; res[p+3][q+j] = x+1; } res[p+0][q+0] = x; res[p+1][q+w-2] = x+2; res[p+1][q+w-1] = x+3; res[p+2][q+0] = x; res[p+2][q+1] = x+1; res[p+3][q+w-1] = x+3; return; } else{ rep(j,w){ res[p+0][q+j] = x; res[p+h-1][q+j] = x+2; } rep(i,1,h-1){ res[p+i][q+0] = x+1; res[p+i][q+1] = x+2; } res[p+1][q+1] = x; res[p+2][q+1] = x+1; f(f,p+1,q+2,h-2,w-2,x+3); return; } }; f(f,0,0,h,w,1); return res; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); #ifdef LOCAL { debug("C"); ll m = 20; set s; vpll p; rep(i,3,m+1){ s.emplace(4,i); s.emplace(i,4); } for(auto [x,w]:s){ if(x > m || w> m){continue;} s.emplace(x+1,w+2); s.emplace(x+2,w+1); rep(i,1,10)rep(j,1,10){ s.emplace(x*i,w*j); } } rep(x,2,m+1){ rep(y,x,m+1){ if(s.count({x,y}) == 0){ debug(x,y); } } } } { debug("T"); ll m = 20; set s; vpll p; rep(i,4,m+1){ s.emplace(4,i); s.emplace(i,4); } rep(i,6,m+1){ s.emplace(3,i); s.emplace(i,3); } for(auto [x,w]:s){ if(x > m || w> m){continue;} if(1){ s.emplace(x+2,w+2); } rep(i,1,10)rep(j,1,10){ s.emplace(x*i,w*j); } } rep(x,2,m+1){ rep(y,x,m+1){ if(s.count({x,y}) == 0){ debug(x,y); } } } } { debug("CT"); ll m = 20; set s; vpll p; rep(i,4,m+1){ s.emplace(4,i); s.emplace(i,4); } rep(i,3,m+1){ s.emplace(3,i); s.emplace(i,3); } for(auto [x,w]:s){ if(x > m || w> m){continue;} if(1){ s.emplace(x+1,w+2); s.emplace(x+2,w+1); } } rep(x,2,m+1){ rep(y,x,m+1){ if(s.count({x,y}) == 0){ debug(x,y); } } } } #endif LL(h,w); auto ans0 = c(h,w); if(ans0[0][0] == -1){ print(-1); } else{ ll m = 0; rep(i,h)rep(j,w){ chmax(m,ans0[i][j]); } print(m); write(ans0); } auto ans1 = t(h,w); ll check = 1; rep(i,h){ rep(j,w){ if(ans1[i][j] == -1){ check = 0; } } } if(check == 0){ print(-1); } else{ ll m = 0; rep(i,h)rep(j,w){ chmax(m,ans1[i][j]); } print(m); write(ans1); } auto ans2 = ct(h,w); if(ans2[0][0] == -1){ print(-1); } else{ ll m = 0; rep(i,h)rep(j,w){ chmax(m,ans2[i][j]); } print(m); write(ans2); } } /* 1 3 3 3 1 1 3 4 1 2 4 4 2 2 2 4 1 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 3 4 1 2 4 4 4 4 4 4 4 4 2 2 2 2 2 2 2 2 2 4 1 2 2 2 2 4 1 1 2 3 4 4 1 3 3 3 3 4 1 2 2 2 2 2 2 2 2 4 1 1 1 1 1 1 2 3 4 4 1 3 3 3 3 3 3 3 3 4 1 1 1 1 1 1 1 2 1 2 2 2 3 2 3 3 3 3 3 3 3 3 1 1 1 1 1 2 1 2 2 2 3 3 3 3 3 3 2 2 2 2 1 1 2 3 1 3 3 3 1 1 1 3 1 1 2 1 2 2 1 1 2 */ /* C 1 1 1 2 1 2 1 2 1 2 2 2 2 2 2 1 1 2 1 2 2 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 2 1 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 */ /* ??????? 1 2 2 2 2 1 1 5 2 3 1 4 5 5 3 1 4 5 3 3 4 4 4 4 3 1 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 5 2 3 1 4 5 5 5 5 5 5 5 3 1 4 5 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 3 */