{"problem":{"name":"Smaller Sum","description":{"content":"You are given a sequence $A=(A_1,A_2,\\dots,A_N)$ of length $N$. Answer the following $Q$ queries. The $i$\\-th query is as follows: *   Find the sum of the elements among $A_{L_i},A_{L_i+1},\\dots,A_{R","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc339_g"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence $A=(A_1,A_2,\\dots,A_N)$ of length $N$.\nAnswer the following $Q$ queries. The $i$\\-th query is as follows:\n\n*   Find the sum of the elements among $A_{L_i},A_{L_i+1},\\dots,A_{R_i}$ that are not greater than $X_i$.\n\nHere, you need to answer these queries online.  \nThat is, only after you answer the current query is the next query revealed.\nFor this reason, instead of the $i$\\-th query itself, you are given encrypted inputs $\\alpha_i, \\beta_i, \\gamma_i$ for the query. Restore the original $i$\\-th query using the following steps and then answer it.\n\n*   Let $B_0=0$ and $B_i =$ (the answer to the $i$\\-th query).\n*   Then, the query can be decrypted as follows:\n    *   $L_i = \\alpha_i \\oplus B_{i-1}$\n    *   $R_i = \\beta_i \\oplus B_{i-1}$\n    *   $X_i = \\gamma_i \\oplus B_{i-1}$\n\nHere, $x \\oplus y$ denotes the bitwise XOR of $x$ and $y$.\nWhat is bitwise XOR? The bitwise XOR of non-negative integers $A$ and $B$, $A \\oplus B$, is defined as follows:\n\n*   The digit in the $2^k$ place ($k \\geq 0$) of $A \\oplus B$ in binary is $1$ if exactly one of the corresponding digits of $A$ and $B$ in binary is $1$, and $0$ otherwise.\n\nFor example, $3 \\oplus 5 = 6$ (in binary: $011 \\oplus 101 = 110$).\n\n## Constraints\n\n*   All input values are integers.\n*   $1 \\le N \\le 2 \\times 10^5$\n*   $0 \\le A_i \\le 10^9$\n*   $1 \\le Q \\le 2 \\times 10^5$\n*   For the encrypted inputs, the following holds:\n    *   $0 \\le \\alpha_i, \\beta_i, \\gamma_i \\le 10^{18}$\n*   For the decrypted queries, the following holds:\n    *   $1 \\le L_i \\le R_i \\le N$\n    *   $0 \\le X_i \\le 10^9$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_N$\n$Q$\n$\\alpha_1$ $\\beta_1$ $\\gamma_1$\n$\\alpha_2$ $\\beta_2$ $\\gamma_2$\n$\\vdots$\n$\\alpha_Q$ $\\beta_Q$ $\\gamma_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc339_g","tags":[],"sample_group":[["8\n2 0 2 4 0 2 0 3\n5\n1 8 3\n10 12 11\n3 3 2\n3 6 5\n12 0 11","9\n2\n0\n8\n5\n\nThe given sequence is $A=(2,0,2,4,0,2,0,3)$.  \nThis input contains five queries.\n\n*   Initially, $B_0=0$.\n*   The first query is $\\alpha = 1, \\beta = 8, \\gamma = 3$.\n    *   After decryption, we get $L_i = \\alpha \\oplus B_0 = 1, R_i = \\beta \\oplus B_0 = 8, X_i = \\gamma \\oplus B_0 = 3$.\n    *   The answer to this query is $9$. This becomes $B_1$.\n*   The next query is $\\alpha = 10, \\beta = 12, \\gamma = 11$.\n    *   After decryption, we get $L_i = \\alpha \\oplus B_1 = 3, R_i = \\beta \\oplus B_1 = 5, X_i = \\gamma \\oplus B_1 = 2$.\n    *   The answer to this query is $2$. This becomes $B_2$.\n*   The next query is $\\alpha = 3, \\beta = 3, \\gamma = 2$.\n    *   After decryption, we get $L_i = \\alpha \\oplus B_2 = 1, R_i = \\beta \\oplus B_2 = 1, X_i = \\gamma \\oplus B_2 = 0$.\n    *   The answer to this query is $0$. This becomes $B_3$.\n*   The next query is $\\alpha = 3, \\beta = 6, \\gamma = 5$.\n    *   After decryption, we get $L_i = \\alpha \\oplus B_3 = 3, R_i = \\beta \\oplus B_3 = 6, X_i = \\gamma \\oplus B_3 = 5$.\n    *   The answer to this query is $8$. This becomes $B_4$.\n*   The next query is $\\alpha = 12, \\beta = 0, \\gamma = 11$.\n    *   After decryption, we get $L_i = \\alpha \\oplus B_4 = 4, R_i = \\beta \\oplus B_4 = 8, X_i = \\gamma \\oplus B_4 = 3$.\n    *   The answer to this query is $5$. This becomes $B_5$."]],"created_at":"2026-03-03 11:01:14"}}