#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> check(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 Q = (int)T.size();
int N = (int)X.size();
vector<vector<int>> grid(N, vector<int>(N));
for (int i = 0; i < N; ++i) {
grid[0][i] = X[i];
grid[i][0] = Y[i];
}
for (int i = 1; i < N; ++i) {
for (int j = 1; j < N; ++j) {
if (grid[i - 1][j] + grid[i][j - 1] == 0) grid[i][j] = 1;
else grid[i][j] = 0;
}
}
vector<vector<ll>> dp(N, vector<ll>(N));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
dp[i][j] = grid[i][j];
if (i > 0) dp[i][j] += dp[i - 1][j];
if (j > 0) dp[i][j] += dp[i][j - 1];
if (i > 0 && j > 0) dp[i][j] -= dp[i - 1][j - 1];
}
}
std::vector<long long> C(Q, 0);
for (int i = 0; i < Q; ++i) {
int y1 = T[i];
int y2 = B[i];
int x1 = L[i];
int x2 = R[i];
ll res = 0;
if (y1 > 0) res -= dp[y1 - 1][x2];
if (x1 > 0) res -= dp[y2][x1 - 1];
if (x1 > 0 && y1 > 0) res += dp[y1 - 1][x1 - 1];
res += dp[y2][x2];
C[i] = res;
}
return C;
}
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 Q = (int)T.size();
int N = (int)X.size();
if (N <= 2) {
return check(X, Y, T, B, L, R);
}
map<int, int> mp;
int start = (X[1] + Y[1] == 0);
if (start == 1) {
mp[0]++;
}
vector<int> nX, nY;
nX.push_back(start);
nY.push_back(start);
for (int i = 2; i < N; ++i) {
nX.push_back((nX.back() + X[i] == 0));
if (nX.back() == 1) {
mp[1 - i]++;
}
}
for (int i = 2; i < N; ++i) {
nY.push_back((nY.back() + Y[i] == 0));
if (nY.back() == 1) {
mp[i - 1]++;
}
}
// for (auto& u : mp) {
// cout << u.first << " " << u.second << "\n";
// }
// cout << "/\n";
start = (nX[1] + nY[1] == 0);
vector<int> nnX{start}, nnY{start};
if (start == 1) {
mp[0]++;
}
for (int i = 2; i < nX.size(); ++i) {
nnX.push_back((nnX.back() + nX[i] == 0));
if (nnX.back() == 1) {
mp[1 - i]++;
}
}
for (int i = 2; i < nY.size(); ++i) {
nnY.push_back((nnY.back() + nY[i] == 0));
if (nnY.back() == 1) {
if (i - 1 == 3) {
// cout << "HERE = " << i << endl;
}
mp[i - 1]++;
}
}
// for (auto& i : nX) {
// cout << i << " ";
// }
// cout << endl;
// for (auto& i : nY) {
// cout << i << " ";
// }
// cout << endl;
// for (auto& i : nnX) {
// cout << i << " ";
// }
// cout << endl;
// for (auto& i : nnY) {
// cout << i << " ";
// }
// cout << endl;
// for (auto& u : mp) {
// cout << u.first << " " << u.second << "\n";
// }
vector<ll> C(Q);
for (int i = 0; i < Q; ++i) {
int y1 = T[i];
int y2 = B[i];
int x1 = L[i];
int x2 = R[i];
if (y1 == 0 || x1 == 0) {
if (y1 == 0) {
C[i] = X[x1];
} else {
C[i] = Y[y1];
}
continue;
}
if (y1 == 1 || x1 == 1) {
if (y1 == 1) {
C[i] = nX[x1 - 1];
} else {
C[i] = nY[y1 - 1];
}
continue;
}
if (y1 == 2 || x1 == 2) {
if (y1 == 2) {
C[i] = nnX[x1 - 2];
} else {
C[i] = nnY[y1 - 2];
}
continue;
}
// cout << y1 << " " << x1 << " , " << y1 - x1 << endl;
if (mp.count(y1 - x1)) {
C[i] = 1;
} else {
C[i] = 0;
}
}
// vector<ll> res = check(X, Y, T, B, L, R);
// vector<vector<int>> grid(N, vector<int>(N));
// for (int i = 0; i < N; ++i) {
// grid[0][i] = X[i];
// grid[i][0] = Y[i];
// }
// for (int i = 1; i < N; ++i) {
// for (int j = 1; j < N; ++j) {
// if (grid[i - 1][j] + grid[i][j - 1] == 0) grid[i][j] = 1;
// else grid[i][j] = 0;
// }
// }
// for (auto& v : grid) {
// for (auto& u : v) {
// cout << u << " ";
// }
// cout << "\n";
// }
// cout << "\n";
// for (int i = 0; i < Q; ++i) {
// if (res[i] != C[i]) {
//// cout << "WA at #" << i + 1 << " query, expected = " << res[i] << " , got = " << C[i] << endl;;
//// cout << grid[T[i]][L[i]] << endl;
//
// }
// }
return {};
}
/*
10
1 0 1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 1 1
10
0 1 0 1 1 1 0 1 0 1
0 1 0 0 1 0 0 1 0 0
*/
/*
4
1 0 1 0
1 1 0 1
2
0 0 0 0
1 1 3 3
*/
