在一个沿海的小镇上，有 $n$ 栋房子，编号为 $1$ 到 $n$，它们从左到右排成一排。每栋房子里都有一个装有零钱的陶瓷存钱罐——第 $j$ 栋房子里的存钱罐恰好含有 $x_j$ 库纳（kuna）。

镇上出现了一个盗贼，他闯入民宅，“劫富济贫”。具体来说，盗贼会选择一栋起始房子 $l$，然后沿着街道向右移动，直到房子 $r$，并在此期间闯入介于 $l$ 和 $r$ 之间（包括首尾）的所有房子。在行动开始时，他的口袋里有 $y$ 库纳。在每栋房子里，他都会砸碎存钱罐，并将找到的金额与他当前口袋里的金额进行比较：

• 如果他当前口袋里的钱较少，他就会从找到的钱中拿走 $1$ 库纳放入自己的口袋。
• 如果他当前口袋里的钱较多，他就会从口袋里拿出 $1$ 库纳留在房子里。
• 如果两者的金额相等，则什么也不做。

现在有 $m$ 个可能的盗窃场景。对于第 $j$ 个场景，已知起始房子 $l_j$、结束房子 $r_j$ 以及该盗贼在行动开始时口袋里的金额 $y_j$。对于每个场景，请确定盗贼在行动结束时口袋里会有多少钱。

输入格式

第一行包含两个自然数 $n$ 和 $m$ —— 房子的数量和盗窃场景的数量。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ —— 每个存钱罐中的金额。

接下来的 $m$ 行中，第 $j$ 行包含三个整数 $l_j$、$r_j$ 和 $y_j$，描述第 $j$ 个盗窃场景。

输出格式

输出 $m$ 行。在第 $j$ 行中，输出第 $j$ 个场景下行动结束时盗贼口袋里的金额。

数据范围

在所有子任务中，满足 $0 \le x_i \le 10^6$，$1 \le l_j \le r_j \le n$ 且 $0 \le y_j \le 10^6$。

样例

输入样例 1

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

输出样例 1

6
3
4

输入样例 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

输出样例 2

6
7
6
6
7