In a small town on the coast, there are $n$ houses labeled with numbers from $1$ to $n$, arranged in a row in that exact order from left to right. In each house, there is a ceramic piggy bank with small change for groceries — the piggy bank in house $j$ contains exactly $x_j$ kuna.

A criminal has appeared in the town who breaks into houses, stealing from the rich and giving to the poor. Specifically, the criminal chooses a starting house $l$ and moves down the street to the right until house $r$, breaking into all houses between house $l$ and house $r$ (both inclusive). At the beginning of his criminal spree, he has $y$ kuna in his pocket. In each house, he breaks the piggy bank and compares the amount found with what he currently has in his pocket:

• If he currently has less money in his pocket, he takes one kuna from the amount found and puts it into his pocket.
• If he currently has more money in his pocket, he takes one kuna from his pocket and leaves it in the house.
• If he has an equal amount of money, he does nothing.

You are presented with $m$ possible robbery scenarios. For the $j$-th scenario, the starting house $l_j$, the ending house $r_j$, and the amount $y_j$ that the local "burglar" had in his pocket at the beginning of the spree are known. For each scenario, determine how much money the thief would have at the end of the spree.

Input

The first line contains the natural numbers $n$ and $m$ — the number of houses and the number of robbery scenarios. The second line contains $n$ integers $x_1, x_2, \dots, x_n$ — the amount of money in each piggy bank. Each of the next $m$ lines contains three integers — $l_j$, $r_j$, and $y_j$, which describe the $j$-th robbery scenario.

Output

Print $m$ lines. In the $j$-th line, print the required amount of money at the end of the spree for the $j$-th scenario.

Subtasks

In all subtasks, $0 \le x_i \le 10^6$, $1 \le l_j \le r_j \le n$, and $0 \le y_j \le 10^6$.

Examples

Input 1

10 3
3 5 5 4 3 6 10 0 4 7
2 10 9
6 6 2
2 8 4

Output 1

6
3
4

Input 2

8 5
2 3 0 9 2 6 0 6
5 6 8
3 4 7
3 8 8
8 8 7
6 7 9

Output 2

6
7
6
6
7