#1189507 (C++23) No.3742 Re: Verse X

• 問題: No.3742 Re: Verse X
• ユーザー: soryuusi0219
• 提出日時: 2026-09-19 17:54:33
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 21,384 bytes
• コンパイル時間: 2,657 ms
• コンパイル使用メモリ: 363,268 KB
• 実行使用メモリ: 12,228 KB
• 最終ジャッジ日時: 2026-09-19 17:54:49
• 合計ジャッジ時間: 6,515 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 39 WA * 18

ソースコード

#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define GET4(_1,_2,_3,NAME,...) NAME
#define GET5(_1,_2,_3,_4,NAME,...) NAME
#define GET6(_1,_2,_3,_4,_5,NAME,...) NAME
#define GET11(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define rep1(i, n)  for(long long i=0;i<(long long)(n);i++)
#define rep2(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define rep3(i,k,n,s) for(long long i=k;i<(long long)(n);i+=(s))
#define rep(...) GET5(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(i,n) for(long long i=(n)-1ll;i>-1ll;i--)
#define per2(i,k,n) for(long long i=(n)-1ll;i>(long long)(k)-1ll;i--)
#define per3(i,k,n,s) for(long long i=(n)-1ll;i>(long long)(k)-1ll;i-=(s))
#define per(...) GET5(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define ub(v,k) (upper_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define dame(...) {out(__VA_ARGS__);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define readi1(n0) ll n0; cin >> (n0);
#define readi2(n0,n1) ll n0,n1; cin >> (n0) >> (n1);
#define readi3(n0,n1,n2) ll n0,n1,n2; cin >> (n0) >> (n1) >> (n2);
#define readi4(n0,n1,n2,n3) ll n0,n1,n2,n3; cin >> (n0) >> (n1) >> (n2) >> (n3);
#define readi5(n0,n1,n2,n3,n4) ll n0,n1,n2,n3,n4; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4);
#define readi6(n0,n1,n2,n3,n4,n5) ll n0,n1,n2,n3,n4,n5; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5);
#define readi7(n0,n1,n2,n3,n4,n5,n6) ll n0,n1,n2,n3,n4,n5,n6; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6);
#define readi8(n0,n1,n2,n3,n4,n5,n6,n7) ll n0,n1,n2,n3,n4,n5,n6,n7; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6) >> (n7);
#define readi9(n0,n1,n2,n3,n4,n5,n6,n7,n8) ll n0,n1,n2,n3,n4,n5,n6,n7,n8; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6) >> (n7) >> (n8);
#define readi10(n0,n1,n2,n3,n4,n5,n6,n7,n8,n9) ll n0,n1,n2,n3,n4,n5,n6,n7,n8,n9; cin >> (n0) >> (n1) >> (n2) >> (n3) >> (n4) >> (n5) >> (n6) >> (n7) >> (n8) >> (n9);
#define readi(...) GET11(__VA_ARGS__, readi10, readi9, readi8, readi7, readi6, readi5, readi4, readi3, readi2, readi1)(__VA_ARGS__)
#define readll(...) readi(__VA_ARGS__)
#define readvi1(v,n) vi v(n); rep(i,(n)) cin >> (v)[i];
#define readvi2(v,w,n) vi v(n),w(n); rep(i,(n)) cin >> (v)[i] >> (w)[i];
#define readvi3(v,w,x,n) vi v(n),w(n),x(n); rep(i,(n)) cin >> (v)[i] >> (w)[i] >> (x)[i];
#define readvi4(v,w,x,y,n) vi v(n),w(n),x(n),y(n); rep(i,(n)) cin >> (v)[i] >> (w)[i] >> (x)[i] >> (y)[i];
#define readvi(...) GET6(__VA_ARGS__, readvi4, readvi3, readvi2, readvi1)(__VA_ARGS__)
#define readvll(...) readvll(__VA_ARGS__)
#define reads1(n) string n; cin >> (n);
#define reads2(n,m) string n,m; cin >> (n) >> (m);
#define reads3(n,m,l) string n,m,l; cin >> (n) >> (m) >> (l);
#define reads4(n,m,l,k) string n,m,l,k; cin >> (n) >> (m) >> (l) >> (k);
#define reads(...) GET5(__VA_ARGS__, reads4, reads3, reads2, reads1)(__VA_ARGS__)
#define readvs(v,n) vs v(n); rep(i,(n)) cin >> (v)[i];
#define readd1(n) ld n; cin >> (n);
#define readd2(n,m) ld n,m; cin >> (n) >> (m);
#define readd3(n,m,l) ld n,m,l; cin >> (n) >> (m) >> (l);
#define readd4(n,m,l,k) ld n,m,l,k; cin >> (n) >> (m) >> (l) >> (k);
#define readd(...) GET5(__VA_ARGS__, readd4, readd3, readd2, readd1)(__VA_ARGS__)
#define readvvi(v,n,m) vvi v((n),vi(m)); rep(i,(n))rep(j,(m)) cin >> (v)[i][j];
#define readvvs(v,n,m) vvs v((n),vs(m)); rep(i,(n))rep(j,(m)) cin >> (v)[i][j];
#define readvpi(v,n) vpi v(n); rep(i,(n)) cin >> (v)[i].fi >> (v)[i].se;
#define readg(G,n,m) vvi G(n);rep(i,m){readi(a,b);a--;b--;G[a].push_back(b);G[b].push_back(a);}
#define readgd(G,n,m) vvi G(n);rep(i,m){readi(a,b);a--;b--;G[a].push_back(b);}
#define readgdrev(G,n,m) vvi G(n);rep(i,m){readi(a,b);a--;b--;G[b].push_back(a);}
#define readt(G,n) vvi G(n);rep(i,n-1){readi(a,b);a--;b--;G[a].push_back(b);G[b].push_back(a);}
#define sz(a) ((ll)(a).size())
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<class T> using P = pair<T,T>;
template<class T> using PP = tuple<T,T,T>;
template<class T> using PPP = tuple<T,T,T,T>;
using pi = P<ll>;
using ppi = PP<ll>;
using pppi = PPP<ll>;
using pll = P<ll>;
using ppll = PP<ll>;
using pppll = PPP<ll>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T> using VVV = vector<vector<vector<T>>>;
template<class T> using VVVV = vector<vector<vector<vector<T>>>>;
using vi=V<ll>;
using vvi=VV<ll>;
using vvvi=VVV<ll>;
using vvvvi=VVVV<ll>;
using vll=V<ll>;
using vvll=VV<ll>;
using vvvll=VVV<ll>;
using vvvvll=VVVV<ll>;
using vpi=V<pi>;
using vvpi=VV<pi>;
using vppi=V<ppi>;
using vvppi=VV<ppi>;
using vpppi=V<pppi>;
using vvpppi=VV<pppi>;
using vpll=V<pll>;
using vvpll=VV<pll>;
using vppll=V<ppll>;
using vvppll=VV<ppll>;
using vpppll=V<pppll>;
using vvpppll=VV<pppll>;
using vb=V<bool>;
using vvb=VV<bool>;
using vs=V<string>;
using vvs=VV<string>;
const ll inf=(1 << 30);
const ll Inf=((ll)1 << 40);
const ll INf=((ll)1 << 50);
const ll INF=((ll)1 << 60);
const double eps=1e-10;
template<class T> using PQ = priority_queue<T>;
template<class T> using SPQ = priority_queue<T,vector<T>,greater<T>>;
/////////////////////////////////////////////////////////
using lll = __int128_t;
using ulll = __uint128_t;
const lll infinf=((lll)1 << 65);
const lll Infinf=((lll)1 << 75);
const lll INfinf=((lll)1 << 85);
const lll INFinf=((lll)1 << 95);
const lll INFInf=((lll)1 << 105);
const lll INFINf=((lll)1 << 115);
const lll INFINF=((lll)1 << 125);
istream &operator>>(istream &is, lll& v) {
  string s; is >> s;
  v = 0;
  for(char c:s){if(isdigit(c))v=v*10+(c-'0');}
  if(s[0]=='-') v*=-1;
  return is;
}
ostream &operator<<(ostream &os, lll v) {
  if(!ostream::sentry(os)) return os;
  char buf[64];
  char *d=end(buf);
  ulll tmp = (v<0?-v:v);
  do{d--;*d=char(tmp%10+'0');tmp/=10;}while(tmp);
  if(v<0) {d--;*d = '-';}
  int len=end(buf)-d;
  if(os.rdbuf()->sputn(d, len)!=len){os.setstate(ios_base::badbit);}
  return os;
}
istream &operator>>(istream &is, ulll& v) {
  string s; is >> s;
  v = 0;
  for(char c:s){if(isdigit(c))v=v*10+(c-'0');}
  return is;
}
ostream &operator<<(ostream &os, ulll v) {
  if(!ostream::sentry(os)) return os;
  char buf[64];
  char *d=end(buf);
  do{d--;*d=char(v%10+'0');v/=10;}while(v);
  int len=end(buf)-d;
  if(os.rdbuf()->sputn(d, len)!=len){os.setstate(ios_base::badbit);}
  return os;
}
//////////////////////////////////////////////////////////  
template<class T> ostream &operator<<(ostream &os, vector<vector<vector<T>>> v);
template<class T> ostream &operator<<(ostream &os, vector<vector<T>> v);
template<class T> istream &operator>>(istream &is, vector<T>& v);
template<class T> ostream &operator<<(ostream &os, vector<T> v);
template<class S, class T> istream &operator>>(istream &is, pair<S,T>& p);
template<class S, class T> ostream &operator<<(ostream &os, pair<S,T> p);
template<class... T> istream &operator>> (istream &is, tuple<T...>& p);
template<class... T> ostream &operator<< (ostream &os, tuple<T...> p);
template<class T> ostream &operator<<(ostream &os, set<T> s);
template<class T> ostream &operator<<(ostream &os, multiset<T> s);
template<class S, class T> ostream &operator<<(ostream &os, map<S,T> m);
template<class S, class T> ostream &operator<<(ostream &os, multimap<S,T> m);
template<class T> ostream &operator<<(ostream &os, queue<T> qu);
template<class T> ostream &operator<<(ostream &os, stack<T> st);
template<class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> qu);
//////////////////////////////////////////////////////////
ostream &operator<<(ostream &os, vector<bool> v){for(bool x : v) os << x; return os;}
ostream &operator<<(ostream &os, vector<vector<bool>> v){for(vector<bool>&x : v) os << x << "\n"; return os;}
template<class T> ostream &operator<<(ostream &os, vector<vector<vector<T>>> v){for(vector<vector<T>> &w : v)for(vector<T> &x : w) os << x << "\n"; return os;}
template<class T> ostream &operator<<(ostream &os, vector<vector<T>> v){for(vector<T> &x : v) os << x << "\n"; return os;}
template<class T> istream &operator>>(istream &is, vector<T>& v){for(T &x : v) is >> x; return is;}
template<class T> ostream &operator<<(ostream &os, vector<T> v){for(T &x : v) os << x << " "; return os;}
template<class S, class T> istream &operator>>(istream &is, pair<S,T>& p){is >> p.fi >> p.se; return is;}
template<class S, class T> ostream &operator<<(ostream &os, pair<S,T> p){if(&os == &cerr) return os << "(" << p.fi << "," << p.se << ")"; else return os << p.fi << " " << p.se;}
template<class Tuple, size_t ...I> array<int,sizeof...(I)>tuple_cin(istream &is, Tuple&& t, index_sequence<I...>){return {{ (void(is >> get<I>(t)), 0)... }};}
template<class... T> istream &operator>> (istream &is, tuple<T...>& p){tuple_cin(is, p, make_index_sequence<tuple_size<decay_t<tuple<T...>>>::value>{}); return is;}
template<class Tuple, size_t ...I> array<int,sizeof...(I)>tuple_cout(ostream &os, Tuple&& t, index_sequence<I...>){if(&os == &cerr) return {{ (void(os << get<I>(t) << ","), 0)... }};return {{ (void(os << get<I>(t) << " "), 0)... }};}
template<class... T> ostream &operator<< (ostream &os, tuple<T...> p){if(&os == &cerr) os << "("; tuple_cout(os, p, make_index_sequence<tuple_size<decay_t<tuple<T...>>>::value>{}); if(&os == &cerr) os << ")"; return os;}
template<class T> ostream &operator<<(ostream &os, set<T> s){if(&os == &cerr) os << "set["; for(T x : s) os << x << " "; if(&os == &cerr) os << "]"; return os;}
template<class T> ostream &operator<<(ostream &os, multiset<T> s){if(&os == &cerr) os << "multiset["; for(T x : s) os << x << " "; if(&os == &cerr) os << "]"; return os;}
template<class T> ostream &operator<<(ostream &os, unordered_set<T> s){if(&os == &cerr) os << "unordered_set["; for(T x : s) os << x << " "; if(&os == &cerr) os << "]"; return os;}
template<class T> ostream &operator<<(ostream &os, unordered_multiset<T> s){if(&os == &cerr) os << "unordered_multiset["; for(T x : s) os << x << " "; if(&os == &cerr) os << "]"; return os;}
template<class S, class T> ostream &operator<<(ostream &os, map<S,T> m){if(&os == &cerr) os << "map["; for(auto [k, v] : m) os << "(" << k << "," << v << ") "; if(&os == &cerr) os << "]"; return os;}
template<class S, class T> ostream &operator<<(ostream &os, multimap<S,T> m){if(&os == &cerr) os << "multimap["; for(auto [k, v] : m) os << "(" << k << "," << v << ") "; if(&os == &cerr) os << "]"; return os;}
template<class S, class T> ostream &operator<<(ostream &os, unordered_map<S,T> m){if(&os == &cerr) os << "unordered_map["; for(auto [k, v] : m) os << "(" << k << "," << v << ") "; if(&os == &cerr) os << "]"; return os;}
template<class S, class T> ostream &operator<<(ostream &os, unordered_multimap<S,T> m){if(&os == &cerr) os << "unordered_multimap["; for(auto [k, v] : m) os << "(" << k << "," << v << ") "; if(&os == &cerr) os << "]"; return os;}
template<class T> ostream &operator<<(ostream &os, queue<T> qu){if(&os == &cerr) os << "queue["; while(!qu.empty()){os << qu.front() << " ";qu.pop();} if(&os == &cerr) os << "]"; return os;}
template<class T> ostream &operator<<(ostream &os, stack<T> st){if(&os == &cerr) os << "stack["; while(!st.empty()){os << st.top() << " ";st.pop();} if(&os == &cerr) os << "]"; return os;}
template<class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> qu){if(&os == &cerr) os << "prioroty_queue["; while (!qu.empty()){os << qu.top() << " ";qu.pop();} if(&os == &cerr) os << "]"; return os;}
//////////////////////////////////////////////////////////
template<class... Ts> void read(Ts&... a) {(cin >> ... >> a);}
void out0(float a){cout<<fixed<<setprecision(15)<<a;}
void out0(double a){cout<<fixed<<setprecision(15)<<a;}
void out0(ld a){cout<<fixed<<setprecision(15)<<a;}
template<class T> void out0(T a){cout<<a;}
template<class T>void out(T a) {out0(a); cout << "\n";}
template<class T, class... Ts>void out(T a, Ts... b) {out0(a); cout << " "; out(b...);}
template<class... Ts>void outf(Ts... a) {out(a...); cout << flush;}

void out0d(float a){cerr<<fixed<<setprecision(15)<<a;}
void out0d(double a){cerr<<fixed<<setprecision(15)<<a;}
void out0d(ld a){cerr<<fixed<<setprecision(15)<<a;}
template<class T> void out0d(T a){cerr<<a;}
template<class T>void outd(T a) {out0d(a); cerr << endl;}
template<class T, class... Ts>void outd(T a, Ts... b) {out0d(a); cerr << " "; outd(b...);}
//////////////////////////////////////////////////////////
template<class T> vector<T> &operator++(vector<T>& v){for(T& x : v) x++; return v;}
template<class T> vector<T> &operator--(vector<T>& v){for(T& x : v) x--; return v;}
template<class T> vector<T> operator++(vector<T>& v, signed){auto res = v; for(T& x : v) x++; return res;}
template<class T> vector<T> operator--(vector<T>& v, signed){auto res = v; for(T& x : v) x--; return res;}
template<class T> vector<T> operator+=(vector<T>& v, const vector<T>& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] += w[i]; return v;}
template<class T> vector<T> operator-=(vector<T>& v, const vector<T>& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] -= w[i]; return v;}
template<class T> vector<T> operator*=(vector<T>& v, const vector<T>& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] *= w[i]; return v;}
template<class T> vector<T> operator/=(vector<T>& v, const vector<T>& w){if(v.size() < w.size()) v.resize(w.size()); for(int i = 0; i < (int)w.size(); i++) v[i] /= w[i]; return v;}
template<class T> vector<T> operator+(vector<T> v, const vector<T>& w){return (v += w);}
template<class T> vector<T> operator-(vector<T> v, const vector<T>& w){return (v -= w);}
template<class T> vector<T> operator*(vector<T> v, const vector<T>& w){return (v *= w);}
template<class T> vector<T> operator/(vector<T> v, const vector<T>& w){return (v /= w);}
template<class T> vector<T> operator*=(vector<T>& v, T w){for(T& x : v) x*=w; return v;}
template<class T> vector<T> operator/=(vector<T>& v, T w){for(T& x : v) x/=w; return v;}
template<class T> vector<T> operator*(vector<T> v, T x){return (v *= x);}
template<class T> vector<T> operator/(vector<T> v, T x){return (v /= x);}
template<class S, class T> pair<S,T> operator+=(pair<S,T>& p, const pair<S,T>& q){p.fi+=q.fi, p.se+=q.se; return p;}
template<class S, class T> pair<S,T> operator+(pair<S,T> p, const pair<S,T>& q){return (p += q);}
template<class S, class T> pair<S,T> operator-=(pair<S,T>& p, const pair<S,T>& q){p.fi-=q.fi, p.se-=q.se; return p;}
template<class S, class T> pair<S,T> operator-(pair<S,T> p, const pair<S,T>& q){return (p -= q);}
//////////////////////////////////////////////////////////
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void posimp(T b){if(b)out("possible");else out("impossible");}
template<class T> void PosImp(T b){if(b)out("Possible");else out("Impossible");}
template<class T> void POSIMP(T b){if(b)out("POSSIBLE");else out("IMPOSSIBLE");}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> T dist_sq(P<T> x, P<T> y){return (x.fi-y.fi)*(x.fi-y.fi)+(x.se-y.se)*(x.se-y.se);}
template<class T> T cross_product(P<T> x, P<T> y){return x.fi * y.se - x.se * y.fi;}
template<class T> bool compare_by_arg(P<T> x, P<T> y){if(x == y) return false; if(x.fi == 0 && x.se == 0) return true; if(y.fi == 0 && y.se == 0) return false; if(x.se >= 0 && y.se < 0) return true; if(x.se < 0 && y.se >= 0) return false; if(x.se == 0 && y.se == 0) return x.fi > y.fi; return x.fi * y.se > x.se * y.fi;}
template<class T> void argsort(V<P<T>>& a){sort(all(a),compare_by_arg<T>);} 
const vpi adj = {{1,0},{0,1},{-1,0},{0,-1}};
const vpi king = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
const vpi knight = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
void outs(ll a,ll b,ll i){if(abs(a)>=i-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return abs(a);return gcd(abs(b),abs(a)%abs(b));}
ll lcm(ll a,ll b){if(!a||!b) return 0; return abs((a / gcd(a,b)) * b);}
template<class T> T POW(T a, ll b){T res=1;while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;}
ll divfloor(ll a, ll b){return (a >= 0 ? a/b : (a-b+1)/b);}
ll divceil(ll a, ll b){return (a >= 0 ? (a+b-1)/b : a/b);}
ll modpow(ll a,ll b,ll modd){ll res=1;a%=modd;while(b){if(b&1)res=res*a%modd;a=a*a%modd;b>>=1;}return res;}
ll sqrtll(ll a){assert(a >= 0); ll r = (ll)sqrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1) <= a) r++; return r;}
ll cbrtll(ll a){assert(a >= 0); ll r = (ll)cbrtl((ld)a)-1; while(r < 0 || (r+1)*(r+1)*(r+1) <= a) r++; return r;}
ll modinv(ll a, ll b){assert(a); if(a == 1) return 1; if(b == 1) return 0; ll ret = (1ll-b*modinv(b%a, a))/a; ret %= b; if(ret < 0) ret += b; return ret;}

int main(){
  std::cin.tie(nullptr), std::ios_base::sync_with_stdio(false);
  ll TESTCASE = 1;
  // cin >> TESTCASE;
  while(TESTCASE--){
    readi(n);
    readvs(s,n);
    if(n >= 11){
      vvb a(n, vb(n,0));
      rep(i,n)rep(j,n) a[i][j] = (s[i][j] == '#');

      vvb v3(n,vb(n,0));
      vvb v5(n,vb(n,0));
      vvb v7(n,vb(n,0));

      auto op3 = [&](ll i, ll j){
        v3[i][j] = !v3[i][j];
        a[i][j] = !a[i][j];
        a[i+1][j+1] = !a[i+1][j+1];
        a[i-1][j+1] = !a[i-1][j+1];
        a[i+1][j-1] = !a[i+1][j-1];
        a[i-1][j-1] = !a[i-1][j-1];
      };
      auto op5 = [&](ll i, ll j){
        v5[i][j] = !v5[i][j];
        a[i][j] = !a[i][j];
        rep(k,1,3){
          a[i+k][j+k] = !a[i+k][j+k];
          a[i-k][j+k] = !a[i-k][j+k];
          a[i+k][j-k] = !a[i+k][j-k];
          a[i-k][j-k] = !a[i-k][j-k];
        }
      };
      auto op7 = [&](ll i, ll j){
        v7[i][j] = !v7[i][j];
        a[i][j] = !a[i][j];
        rep(k,1,4){
          a[i+k][j+k] = !a[i+k][j+k];
          a[i-k][j+k] = !a[i-k][j+k];
          a[i+k][j-k] = !a[i+k][j-k];
          a[i-k][j-k] = !a[i-k][j-k];
        }
      };


      per(i,n-2) per(j,n-2) if(a[i+2][j+2]) op3(i+1,j+1);

      if(a[0][n-1] || a[1][n-1] || a[n-1][0] || a[n-1][1]) dame(-1);

      rep(j,n-2) if(a[0][j]) op3(1,j+1);
      rep(i,n-2) if(a[i][0]) op3(i+1,1);

      if(a[0][n-1] || a[0][n-2] || a[n-1][0] || a[n-2][0]) dame(-1);

      rep(j,1,n-3) if(a[1][j]) op3(2,j+1);
      rep(i,1,n-3) if(a[i][1]) op3(i+1,2);
      if(a[1][n-2]) op3(2,n-3);
      if(a[n-2][1]) op3(n-3,2);

      if(a[1][n-3]){
        op5(2,n-4);
        op7(3,n-5);
        op3(5,n-3);
        op3(1,n-7);
        op3(2,n-4);
      }
      if(a[1][n-4]){
        op5(2,n-5);
        op7(3,n-6);
        op3(1,n-8);
        op3(2,n-5);
      }
      if(a[n-3][1]){
        op5(n-4,2);
        op7(n-5,3);
        op3(n-3,5);
        op3(n-7,1);
        op3(n-4,2);
      }
      if(a[n-4][1]){
        op5(n-5,2);
        op7(n-6,3);
        op3(n-8,1);
        op3(n-5,2);
      }

      if(a[3][n-2]){
        op5(4,n-3);
        op7(5,n-4);
        op3(7,n-2);
        op3(4,n-3);
      }
      if(a[2][n-2]){
        op5(3,n-3);
        op7(4,n-4);
        op3(6,n-2);
        op3(3,n-3);
      }
      if(a[n-2][3]){
        op5(n-3,4);
        op7(n-4,5);
        op3(n-2,7);
        op3(n-3,4);
      }
      if(a[n-2][2]){
        op5(n-3,3);
        op7(n-4,4);
        op3(n-2,6);
        op3(n-3,3);
      }
      rep(i,2,n-2)rep(j,2,n-2) if(a[i][j]) {
        op5(i,j);
        op3(i-1,j-1);
        op3(i-1,j+1);
        op3(i+1,j-1);
        op3(i+1,j+1);
      }

      vppi ans;
      rep(i,n) rep(j,n) if(v3[i][j]) ans.emplace_back(1,i+1,j+1);
      rep(i,n) rep(j,n) if(v5[i][j]) ans.emplace_back(2,i+1,j+1);
      rep(i,n) rep(j,n) if(v7[i][j]) ans.emplace_back(3,i+1,j+1);

      out(ans.size());
      for(auto [x,y,z] : ans) out(x,y,z);
      return 0;
    }
    // assert(0);

    constexpr ll M = 500;
    using bit = bitset<M>;
    vector<bit> base(n*n);
    vb used(n*n,0);

    vppi ops;
    rep(k,1,(n+1)/2) rep(i,k,n-k) rep(j,k,n-k){
      ll x = ops.size();
      bit w(0);
      w[n*n+x] = 1;
      w[n*i+j] = 1;
      rep(l,1,k+1) {
        w[(i+l)*n+j+l] = 1;
        w[(i+l)*n+j-l] = 1;
        w[(i-l)*n+j+l] = 1;
        w[(i-l)*n+j-l] = 1;
      }
      ops.emplace_back(k,i+1,j+1);
      rep(t,n*n) if(w[t]){
        if(used[t])  w ^= base[t];
        else {
          base[t] = w;
          used[t] = 1;
          break;
        }
      }
    }
    // outd(ops);
    ll m = ops.size();
    bit w(0);
    rep(i,n)rep(j,n) if(s[i][j] == '#') w[i*n+j] = 1;
    // out(w);
    rep(t,n*n) if(w[t]){
      if(used[t])  w ^= base[t];
      else dame(-1)
    }
    // out(w);
    vppi ans;
    rep(i,m) if(w[n*n+i]) ans.push_back(ops[i]);
    out(ans.size());
    for(auto [x,y,z] : ans) out(x,y,z);
  }
}