Bugged Modular Sum Query

Nauuo is a girl who loves programming. One day, she encountered a problem that asks her to compute the following: Given an array \( a_1, a_2, \dots, a_n \) and an integer \( p \), answer \( m \) queries. In each query, you are given three integers \( l \), \( r \) and \( x \), and you have to compute the value of the function Sum(a, l, r, x, p).

The function is defined in the buggy pseudocode below. Note that the helper function ModAdd adds two integers in the following way:

[ \text{ModAdd}(x, y, p) = \begin{cases} x+y-p & \text{if } x+y \ge p,\ x+y & \text{if } x+y < p. \end{cases} ]

The function Sum is defined as follows:

function Sum(a, l, r, x, p):
    for i from l to r:
        if x + a[i] \ge p:
            x = x + a[i] - p
        else:
            x = x + a[i]
    return x

In other words, starting with the initial value \( x \), you add each element \( a_i \) from index \( l \) to \( r \) one by one. For each addition, if the sum \( x + a[i] \) is at least \( p \), you subtract \( p \) exactly once. Note that this is not the same as taking the sum modulo \( p \), because if the intermediate sum exceeds \( 2p \) or more, only one subtraction is performed.

Your task is to compute the value returned by the function for each query. You may assume that the integers will not overflow.

inputFormat

The first line of input contains three integers \( n \), \( m \) and \( p \).

The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \).

Each of the next \( m \) lines contains three integers \( l \), \( r \) and \( x \) describing a query.

outputFormat

For each query, output a single line containing the return value of Sum(a, l, r, x, p).

sample

5 3 8
3 2 7 1 9
1 3 5
2 5 0
1 5 7

1
3
5