#include using namespace std; #if __has_include() #include using namespace atcoder; #endif #ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #include template ostream& operator<<(ostream& os, const pair& p) {return os<<'(' < ostream& operator<<(ostream& os, const vector& v) {os<<'[';for(auto it=v.begin();it!=v.end();++it){os<<*it; if(next(it)!=v.end()){os<<", ";}}return os<<']';} template ostream& operator<<(ostream& os, const vector>& vv) {os<<"[\n";for(auto it=vv.begin();it!=vv.end();++it){os<<" "<<*it;if(next(it)!=vv.end()){os<<",\n";}else{os<<"\n";}}return os<<"]";} #define dump(x) cerr << #x << " = " << (x) << '\n' #else #define dump(x) (void)0 #endif using ll = long long; using ld = long double; using P = pair; template using pq = priority_queue; template using pq_g = priority_queue, greater>; #define out(x) cout<{}; (i) != (n); ++(i)) #define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i)) #define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__) template inline bool chmin(T& a, T b) {if(a > b){a = b; return true;} else {return false;}}; template inline bool chmax(T& a, T b) {if(a < b){a = b; return true;} else {return false;}}; const ll INF=(1LL<<60); const ll mod=998244353; using Graph = vector>; using Network = vector>>; using Grid = vector; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; const int dx2[8] = {1, 1, 1, 0, 0, -1, -1, -1}; const int dy2[8] = {1, 0, -1, 1, -1, 1, 0, -1}; static constexpr int MAXW = 10000; using BS = bitset; void solve() { int H,W; if(!(cin>>H>>W)) return; if (W > MAXW) { vector g(H, string(W,'X')); auto ok = [&](int y,int x,char ch) -> bool { if (x>=2 && g[y][x-1]==ch && g[y][x-2]==ch) return false; if (y>=2 && g[y-1][x]==ch && g[y-2][x]==ch) return false; if (y>=2 && x>=2 && g[y-1][x-1]==ch && g[y-2][x-2]==ch) return false; if (y>=2 && x+2 g(H, string(W,'X')); function build_row = [&](int y, const BS& p1, const BS& p2) -> bool { vector cur(W,-1); BS rowBits; function dfs = [&](int x) -> bool { if (x==W){ for(int i=0;i=2 && cur[x-1]==c && cur[x-2]==c) continue; if (y>=2 && (int)p1.test(x)==c && (int)p2.test(x)==c) continue; if (y>=2 && x>=2 && (int)p1.test(x-1)==c && (int)p2.test(x-2)==c) continue; if (y>=2 && x+2