#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<ll> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r) {
int n = x.size(), q = t.size();
vector<ll> ans(q);
queue<pii> Q;
map<pii, int> val;
for(int i=0; i<n; i++) {
val[{ 0, i }] = x[i];
val[{ i, 0 }] = y[i];
}
Q.push({ 1, 1 });
val[{ 1, 1 }] = (val[{ 0, 1 }] + val[{ 1, 0 }] == 0);
int vis = 0;
while(!Q.empty()) {
auto [r, c] = Q.front(); Q.pop();
vis++;
if(min(r+1, c) <= 3 && max(r+1, c) < n && !val.count({ r+1, c })) {
val[{ r+1, c }] = (val[{ r, c }] + val[{ r+1, c-1 }] == 0);
Q.push({ r+1, c });
}
if(min(r, c+1) <= 3 && max(r, c+1) < n && !val.count({ r, c+1 })) {
val[{ r, c+1 }] = (val[{ r, c }] + val[{ r-1, c+1 }] == 0);
Q.push({ r, c+1 });
}
}
assert(vis <= 7*n);
// for(int i=0; i<n; i++) {
// for(int j=0; j<n; j++) cout << val[{ i, j }] << " ";
// cout << endl;
// }
for(int i=0; i<q; i++) {
int r = t[i], c = l[i];
if(min(r, c) <= 2) {
ans[i] = val[{ r, c }];
} else {
int cnt = min(r-3, c-3);
ans[i] = val[{r-cnt, c-cnt}];
}
}
return ans;
}
