#include #include #include #include #include #define getchar getchar_unlocked #define putchar putchar_unlocked inline int in() { int n = 0; short c; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } inline unsigned long long inll() { unsigned long long n = 0; short c; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } inline void out(unsigned long long n) { short res[20], i = 0; do { res[i++] = n % 10, n /= 10; } while (n); while (i) putchar(res[--i] + '0'); putchar('\n'); } const int MAX_N = 50003; const int MAX_Q = 50003; const int WIDTH = 1000; struct info { int lower, upper, color; info(){} info(const int _lower, const int _upper, const int _color) : lower(_lower), upper(_upper), color(_color){} }; info xborder[2 * MAX_N], yborder[2 * MAX_N]; std::vector _index[2 * MAX_N / WIDTH + 1]; std::pair query[MAX_Q]; unsigned long long h[MAX_N], ans[MAX_Q]; unsigned int smx[2 * MAX_N], smy[2 * 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 = in(), b = in(), c = in(), d = in(), e = in(); ++smx[a + 1], ++smx[c + 1], ++smy[b + 1], ++smy[d + 1]; tmp[i] = {a, b, c, d, e}; } for(int i = 0; i < 2 * N; ++i){ smx[i + 1] += smx[i], smy[i + 1] += smy[i]; } for(const std::vector& in : tmp){ const int a = smx[in[0]] + idX[in[0]]++; const int b = smy[in[1]] + idY[in[1]]++; const int c = smx[in[2]] + idX[in[2]]++; const int d = smy[in[3]] + idY[in[3]]++; const int e = in[4]; xborder[a] = {b, d, e}, xborder[c] = {b, d, -e}, yborder[b] = {a, c, e}, yborder[d] = {a, c, -e}; } } void transform_query(){ for(int i = 0; i < Q; ++i){ int p = in(), q = in(); const int x = smx[p + 1] - 1; const int y = smy[q + 1] - 1; if(x < 0 || x >= 2 * N - 1 || y < 0 || y >= 2 * N - 1){ // out of range ans[i] = 0ULL; }else{ query[i] = {x, y}, _index[x / WIDTH].push_back(i); } } } int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); N = in(); for(int i = 1; i <= N; ++i){ h[i] = inll(); } transform_rectangle(); Q = in(); transform_query(); unsigned long long cur_hash = 0; int curx = -1, cury = -1; const int mx = (2 * N - 2) / WIDTH; for(int i = 0; i <= mx; ++i){ if(_index[i].empty()) continue; memset(C, 0, sizeof(C)), cur_hash = 0, curx = i * WIDTH, cury = -1; std::sort(_index[i].begin(), _index[i].end(), [&](const int a, const int b){ return (query[a].second < query[b].second); }); for(int id : _index[i]){ // left while(curx > query[id].first){ if(xborder[curx].lower <= cury && cury < xborder[curx].upper){ const int c = xborder[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(xborder[curx].lower <= cury && cury < xborder[curx].upper){ const int c = xborder[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(yborder[cury].lower <= curx && curx < yborder[cury].upper){ const int c = yborder[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){ out(ans[i]); } return 0; }