#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 L, R;
int sum[4 * 2*N];
int st[4 * 2*N];
void Init(int i, int x, int y, int v=1, int l=L, int r=R) {
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=L, int r=R) {
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_last(int v=1, int l=L, int r=R) {
if (r-l == 1) {
sum[v]--;
return sum[v]==0;
}
int ret = Update_last(RC, mid, r);
sum[v] = sum[LC] + sum[RC];
return ret;
}
void Update_first(int x, int v=1, int l=L, int r=R) {
if (r-l == 1) {
sum[v]++;
st[v] ^= x;
return;
}
Update_first(x, LC, l, mid);
sum[v] = sum[LC] + sum[RC];
}
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<int> row;
row.pb((X[1] | Y[1]) ^ 1);
for (int i=2; i<n; i++) row.pb((row.back() | X[i]) ^ 1);
L=n;
R=n;
for (int i=0; i < n-1;) {
int j = i+1;
while (j < n-1 && row[j-1] != row[j]) j++;
R++;
Init(R-1, j-i, row[i]);
i=j;
}
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();
while (it != all.end() && T[*it]==0) {
ans[*it] = X[LE[*it]];
it++;
}
for (int r=1; r<n; ) {
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_last()) R--;
int x = Get(0);
if (x==1 || (x==0 && Y[r]==0)) Update_first(1);
else {
L--;
Init(L, 1, 0);
}
}
}
return ans;
}
