#include "mosaic.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
#define pb push_back
#define LC (v<<1)
#define RC (v<<1|1)
#define mid ((l+r) >> 1)
const int N = 200200;
int sum[4 * 2*N];
int st[4 * 2*N];
void Init(int i, int x, int y, int v=1, int l=0, int r = 2*N) {
if (r-l == 1) {
sum[v] = x;
st[v] = y;
return;
}
i<mid ? Init(i,x,y, LC, l, mid) : Init(i,x,y, RC, mid, r);
sum[v] = sum[LC] + sum[RC];
}
int Get(int x, int v=1, int l=0, int r = 2*N) {
if (r-l == 1) return st[v] ^ (x%2);
if (0 <= x-sum[LC]) return Get(x-sum[LC], RC, mid, r);
else return Get(x, LC, l, mid);
}
int Update(int i, int x, int y, int v=1, int l=0, int r = 2*N) {
if (r-l == 1) {
sum[v] += x;
st[v] ^= y;
return sum[v]==0;
}
int ret = (i<mid ? Update(i,x,y, LC, l, mid) : Update(i,x,y, RC, mid, r));
sum[v] = sum[LC] + sum[RC];
return ret;
}
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> LE, std::vector<int> RI) {
int n = X.size();
int q = (int)T.size();
if (n==1) return vector<ll> (q, X[0]);
vector<ll> all(q), ans(q);
iota(all.begin(), all.end(), 0);
sort(all.begin(), all.end(), [&](int i, int j) {
return T[i]<T[j];
});
auto it = all.begin();
int r=0;
vector<int> row;
for (int i=1; i<n; i++) row.pb(X[i]);
for (; r<n; ) {
while (it != all.end() && T[*it]==r) {
int c = LE[*it];
if (c==0) ans[*it] = Y[r];
else ans[*it] = row[c-1];
it++;
}
r++;
if (r != n) {
vector<int> new_row;
new_row.pb((Y[r] | row[0]) ^ 1);
for (int i=1; i < n-1; i++) new_row.pb((new_row.back() | row[i]) ^ 1);
swap(row, new_row);
}
bool done = (2 <= r);
for (int i=0; i+2 < row.size(); i++) if (row[i]==0 && row[i+1]==0 && row[i+2]==0) done = false;
if (row[0]==0 && row[1]==0) done = false;
if (done) break;
}
int L=n;
int R=n;
bool one = false;
for (int i=0; i < n-1;) {
int j = i+1;
while (j < n-1 && row[j-1] != row[j]) j++;
Init(R++, j-i, row[i]);
if (i==0 && j==1) one = true;
i=j;
}
for (; r<n;) {
// for (int c=1; c<n; c++) assert(Get(c-1) == (r%2 == c%2));
while (it!=all.end() && T[*it]==r) {
int c = LE[*it];
if (c==0) ans[*it] = Y[r];
else ans[*it] = Get(c-1);
it++;
}
r++;
if (r != n) {
if (Update(R, -1, 0)) R--;
int x = Get(0);
if (x==1 || (x==0 && Y[r]==one)) {
Update(L, 1, 1);
one = false;
}
else {
L--;
Init(L, 1, 0);
one = true;
}
}
}
return ans;
}
