#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define pb push_back #define mp make_pair #define pii pair #define vi vector #define vpii vector #define SZ(x) ((int)(x.size())) #define fi first #define se second #define FOR(i,n) for(int (i)=0;(i)<(n);++(i)) #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i)) #define IN(x,y) ((y).find((x))!=(y).end()) #define ALL(t) t.begin(),t.end() #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i) #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i) #define REMAX(a,b) (a)=max((a),(b)); #define REMIN(a,b) (a)=min((a),(b)); #define DBG cerr << "debug here" << endl; #define DBGV(vari) cerr << #vari<< " = "<< (vari) < dp; int solve(unsigned mask) { if (mask == 0) return 0; auto it = dp.find(mask); if (it != dp.end()) { return it->se; } unordered_set subresults; FOR(i1, R) { REP(i2, i1, R-1) { FOR(j1, R) { REP(j2, j1, R-1) { bool all_ones = true; REP(k1, i1, i2) { REP(k2, j1, j2) { if ((mask & (1U << (k1*R+k2))) == 0) { all_ones = false; break; } } if (!all_ones) { break; } } if (all_ones) { unsigned new_submask = mask; REP(k1, i1, i2) { REP(k2, j1, j2) { new_submask ^= (1U << (k1*R+k2)); } } int subresult = solve(new_submask); subresults.insert(subresult); } } } } } int res = 0; while (1) { auto it = subresults.find(res); if (it == subresults.end()) { break; } ++res; } dp[mask] = res; return res; } unsigned encode(string s[R]) { unsigned res = 0; FOR(i, R) { FOR(j, R) { if (s[i][j] == '1') { res |= (1U << (R*R-1-R*i-j)); } } } return res; } //tree containing values from range [0, M - 1] const int M = 131072; // must be a power of 2 unsigned tree[2 * M]; void insert(int x, unsigned v) { int vx = M + x; tree[vx] = v; while(vx != 1) { vx /= 2; tree[vx] = tree[2 * vx] ^ tree[2 * vx + 1]; } } unsigned query(int a, int b) { int va = M + a, vb = M + b; unsigned res = tree[va]; if(va != vb) res ^= tree[vb]; while(va / 2 != vb / 2) { if(va % 2 == 0) res ^= tree[va + 1]; if(vb % 2 == 1) res ^= tree[vb - 1]; va /= 2; vb /= 2; } return res; } int main() { ios_base::sync_with_stdio(0); for(unsigned bits = 0; bits < (1 << (R*R)); ++bits) { solve(bits); } string tmp[4]; int t; cin >> t; assert(t >= 1 && t <= T); while (t--) { int n, q; cin >> n >> q; assert(n >= 1 && n <= N); assert(q >= 1 && q <= Q); FOR(i, n) { FOR(j, R) { cin >> tmp[j]; } unsigned code = encode(tmp); insert(i, solve(code)); } while (q--) { int qid; cin >> qid; if (qid == 1) { int l, r; cin >> l >> r; assert(l >= 1 && l <= n); assert(r >= 1 && r <= n); assert(l <= r); --l, --r; unsigned res = query(l, r); if (res == 0) { cout << "Lotsy" << endl; } else { cout << "Pishty" << endl; } } else if (qid == 2) { int idx; cin >> idx; assert(idx >= 1 && idx <= n); --idx; FOR(i, R) { cin >> tmp[i]; } unsigned code = encode(tmp); insert(idx, solve(code)); } else assert(false); } } return 0; }