#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)
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) {
int n = X.size();
int q = (int)T.size();
if (n==1) return vector<ll> (q, X[0]);
vector<ll> ans(q);
vector<int> all(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();
vector<int> a;
for (int i=1; i<n; i++) a.pb(X[i]);
for (int r=0; r<2; r++) {
while (it!=all.end() && T[*it]==r) {
int c = L[*it];
if (c==0) ans[*it] = Y[r];
else ans[*it] = a[c-1];
it++;
}
if (r+1 != n) {
vector<int> b;
b.pb((Y[r+1]|a[0])^1);
for (int i=1; i<a.size(); i++) b.pb((b.back()|a[i])^1);
swap(a, b);
}
}
{
vector<int> b = a;
a.clear();
for (int i=0; i<n; i++) a.pb(0);
for (int i:b) a.pb(i);
}
int z=n;
for (int r=2; r<n; r++) {
while (it!=all.end() && T[*it]==r) {
int c = L[*it];
if (c==0) ans[*it] = Y[r];
else ans[*it] = a[z+c-1];
it++;
}
if (r+1 != n) {
z--;
a[z] = (Y[r+1]|a[z+1])^1;
}
}
return ans;
}
