#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
const int MAX_N2 = 5001;
int mat[MAX_N2][MAX_N2];
int matL[4][MAX_N], matC[MAX_N + 1][4];
int diag[2 * MAX_N + 5];
vector<long long> mosaic(vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R) {
int n = X.size();
int q = (int)T.size();
vector<long long> ans(q);
for (int c = 1; c <= n; c++)
matL[1][c] = X[c - 1];
for (int c = 1; c <= 3; c++)
matC[1][c] = X[c - 1];
for (int l = 1; l <= n; l++)
matC[l][1] = Y[l - 1];
for (int l = 1; l <= 3; l++)
matL[l][1] = Y[l - 1];
// for (int l = 2; l <= n; l++) {
// for (int c = 2; c <= n; c++)
// mat[l][c] = !(mat[l][c - 1] | mat[l - 1][c]);
// }
// for (int l = 1; l <= n; l++) {
// for (int c = 1; c <= n; c++)
// printf("%d ", mat[l][c]);
// printf("\n");
// }
for (int d = 0; d <= 2 * n + 1; d++)
diag[d] = -1;
// for (int l = 4; l <= n; l++) {
// for (int c = 4; c <= n; c++) {
// int d = l - c + n;
// if (diag[d] == -1)
// diag[d] = mat[l][c];
// assert(diag[d] == mat[l][c]);
// }
// }
for (int l = 2; l <= 3; l++) {
for (int c = 2; c <= n; c++)
matL[l][c] = !(matL[l][c - 1] | matL[l - 1][c]);
}
for (int c = 2; c <= 3; c++) {
for (int l = 2; l <= n; l++)
matC[l][c] = !(matC[l][c - 1] | matC[l - 1][c]);
}
for (int c = 3; c <= n; c++)
diag[3 - c + n] = matL[3][c];
for (int l = 3; l <= n; l++)
diag[l - 3 + n] = matC[l][3];
// for (int d = 0; d <= 2 * n + 1; d++)
// printf("%d\n", diag[d]);
// for (int l = 1; l <= n; l++) {
// for (int c = 1; c <= n; c++)
// sp[l][c] = mat[l][c] + sp[l][c - 1] + sp[l - 1][c] - sp[l - 1][c - 1];
// }
for (int i = 0; i < q; i++) {
int l1 = T[i] + 1, l2 = B[i] + 1, c1 = L[i] + 1, c2 = R[i] + 1;
if (l2 <= 2)
ans[i] = matL[l2][c2];
else if (c2 <= 2)
ans[i] = matC[l2][c2];
else
ans[i] = diag[l2 - c2 + n];
}
return ans;
}
