P5609 [Ynoi2013] Love for Data Structures

Nauuo is a girl who likes programming. One day she was working on a problem that asked her to compute the sum of some numbers modulo an integer $p$. She wrote the following code, but got WA.  She quickly found the bug: the `ModAdd` function only works for numbers in $[0,p)$, but in this problem the numbers may fall outside this range. She became curious about this incorrect function, so she wants to know what result it actually produces. However, the original code runs too slowly, so she asks you for help. Given an array $a_1,a_2,\ldots,a_n$ and an integer $p$, there are $m$ queries. Each query gives three integers $l$, $r$, and $x$. You need to compute the return value of `Sum(a,l,r,x,p)`. The definition of `Sum` has already been given in the pseudocode above. Note that in the code above, integers will not overflow.

The first line contains three integers $n$, $m$, $p$, representing the length of the array, the number of queries, and the modulus. Note that the modulus is only used in `ModAdd`. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, representing the given array. The next $m$ lines each contain three integers $l$, $r$, and $x$. You need to compute `Sum(a,l,r,x,p)`. **This problem is forced online. All input $l,r,x$ must be XORed with $lastans$, where $lastans$ is defined as (the answer of the previous query) modulo $n$. If the answer is negative, you need to take the modulo to make it positive. If there has been no previous query, then it is $0$.**

Output $m$ integers in order, one per line, representing the answers to the queries.

Idea: rushcheyo&nzhtl1477, Solution: ccz181078, Code: rushcheyo&ccz181078, Data: rushcheyo&nzhtl1477 Constraints: for $100\%$ of the testdata, $1\le n\le10^6$, $1\le m\le2\times 10^5$, $1\le p\le10^9$, $-10^9\le a_i\le10^9$, $1\le l\le r\le n$, $0\le x\le p-1$. Translated by ChatGPT 5