Sequence Propagation and Zeroing Query Cost

Given a sequence \(S\) of length \(N\) at time \(0\), the initial value of the \(i\)-th element is \(S_i(0)=S_i\) for \(1 \le i \le N\), and we define \(S_0(t)=0\) for any \(t\ge0\). For any time \(t\ge1\) and index \(1\le i\le N\), the value at time \(t\) is computed by the recurrence:

[ \begin{cases} S_0(t)=0,\ S_i(0)=S_i,\ S_i(t)=\max{ S_{i-1}(t-1),;S_i(t-1) }. \end{cases} ]

Intuitively, for any \(i\) and time \(t\), if \(t\ge i\) then \(S_i(t)=\max\{S_1,S_2,\dots,S_i\}\); otherwise, \(S_i(t)=\max\{S_{i-t+1},S_{i-t+2},\dots,S_i\}\).

You are given \(Q\) independent operations. The \(j\)-th operation is evaluated independently on the original sequence and is defined as follows: at time \(T_j\), the entire subsequence in the interval \([L_j,R_j]\) is set to zero. The cost to perform this operation is computed as

[ Cost_j = \sum_{k=L_j}^{R_j} S_k(T_j). ]

Your task is to compute and output the cost for each operation.

inputFormat

The first line contains two integers \(N\) and \(Q\) separated by a space.

The second line contains \(N\) integers, representing the initial sequence \(S_1, S_2, \dots, S_N\).

The following \(Q\) lines each contain three integers \(T_j\), \(L_j\), and \(R_j\) describing one operation.

outputFormat

For each operation, output a single line containing the cost to perform that operation.

sample

5 2
3 1 4 1 5
1 2 4
3 3 5

6
13