Problem Description

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.

Input Format

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 Format

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

4 5 6
7 2 -3 17
2 3 1
1 3 3
0 3 0
2 4 2
4 4 0

0
-3
4
12
11

Hint

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