Tempest's Swap and Sum

The problem requires you to bring happiness to all magical girls by solving the Tempest challenge. You are given a sequence \(a_1,\dots,a_n\) and \(m\) operations. In each operation, you are provided with three integers \(x, l, r\). You should process the following steps:

1. Iterate over the sequence from \(a_1\) to \(a_n\) in order. For each element \(a_i\), compare the current value of \(x\) with \(a_i\). If \(x > a_i\), swap \(a_i\) and \(x\).

2. After scanning through the entire sequence, output the sum \(\sum_{i=l}^{r} a_i\).

Note that the sequence is modified by each operation and the modifications carry over to subsequent operations.

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) is the length of the sequence and \(m\) is the number of operations.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the initial sequence.

Each of the next \(m\) lines contains three integers \(x, l, r\) representing an operation.

outputFormat

For each operation, output a single line containing the result of the summation \(\sum_{i=l}^{r} a_i\) after performing the swap operations on the sequence.

sample

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

9
25