#include #include #include #include #include #include const int MAX_N = 50003; const int MAX_Q = 50003; struct info { int lower, upper, color; info() : info(2 * MAX_N + 1, -1, 0){} info(const int _lower, const int _upper, const int _color) : lower(_lower), upper(_upper), color(_color){} }; info upx[2 * MAX_N], upy[2 * MAX_N]; std::pair query[MAX_Q]; unsigned long long h[MAX_N], ans[MAX_Q]; int X[MAX_N], Y[MAX_N], C[MAX_N]; int N, Q; void transform_rectangle(){ std::vector > tmp(N); std::vector idX(2 * N, 0), idY(2 * N, 0); for(int i = 0; i < N; ++i){ int a, b, c, d, e; std::cin >> a >> b >> c >> d >> e; X[2 * i] = a, X[2 * i + 1] = c, Y[2 * i] = b, Y[2 * i + 1] = d; tmp[i] = {a, b, c, d, e}; } std::sort(X, X + 2 * N), std::sort(Y, Y + 2 * N); for(const std::vector& in : tmp){ const int a = std::lower_bound(X, X + 2 * N, in[0]) - X + idX[in[0]]++; const int b = std::lower_bound(Y, Y + 2 * N, in[1]) - Y + idY[in[1]]++; const int c = std::lower_bound(X, X + 2 * N, in[2]) - X + idX[in[2]]++; const int d = std::lower_bound(Y, Y + 2 * N, in[3]) - Y + idY[in[3]]++; const int e = in[4]; upx[a] = {b, d, e}, upx[c] = {b, d, -e}, upy[b] = {a, c, e}, upy[d] = {a, c, -e}; } } void transform_query(std::vector& index){ for(int i = 0; i < Q; ++i){ int p, q; std::cin >> p >> q; const int x = std::upper_bound(X, X + 2 * N, p) - X - 1; const int y = std::upper_bound(Y, Y + 2 * N, q) - Y - 1; if(x < 0 || x >= 2 * N - 1 || y < 0 || y >= 2 * N - 1){ ans[i] = 0ULL; }else{ query[i] = {x, y}, index.push_back(i); } } } int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); std::cin >> N; for(int i = 1; i <= N; ++i){ std::cin >> h[i]; } transform_rectangle(); std::cin >> Q; std::vector index; transform_query(index); const int width = 2 * ceil(sqrt(N)); std::sort(index.begin(), index.end(), [&](const int a, const int b){ const int u = query[a].first / width, v = query[b].first / width; return (u == v) ? (query[a].second < query[b].second) : (u < v); }); unsigned long long cur_hash = 0; int prv = -1, curx = -1, cury = -1; for(const int id : index){ const int cur = query[id].first / width; if(prv != cur){ memset(C, 0, sizeof(C)), cur_hash = 0, prv = cur, curx = cur * width - 1, cury = -1; } // left while(curx > query[id].first){ if(upx[curx].lower <= cury && cury < upx[curx].upper){ const int c = upx[curx].color; if(c > 0){ if(--C[c] == 0) cur_hash ^= h[c]; }else{ if(++C[-c] == 1) cur_hash ^= h[-c]; } } --curx; } // right while(curx < query[id].first){ ++curx; if(upx[curx].lower <= cury && cury < upx[curx].upper){ const int c = upx[curx].color; if(c > 0){ if(++C[c] == 1) cur_hash ^= h[c]; }else{ if(--C[-c] == 0) cur_hash ^= h[-c]; } } } // up while(cury < query[id].second){ ++cury; if(upy[cury].lower <= curx && curx < upy[cury].upper){ const int c = upy[cury].color; if(c > 0){ if(++C[c] == 1) cur_hash ^= h[c]; }else{ if(--C[-c] == 0) cur_hash ^= h[-c]; } } } ans[id] = cur_hash; } for(int i = 0; i < Q; ++i){ std::cout << ans[i] << "\n"; } return 0; }