题目描述

四骑士正在准备一个新的魔术。舞台上有一块魔法板，最初只写着一个数 $S$，表示据称存放在银行保险箱中的金额。

每一步，魔术师可以进行以下操作：

• 选择板上的一个数 $y$。
• 擦掉 $y$。
• 写上两个正整数 $a$ 和 $b$，满足 $y=a+b$。

然而，每次这样的拆分，制作人都需要支付 $a\cdot b$ 枚硬币作为特效费用。

四骑士希望在某个时刻，板上出现预先指定的若干个数。这些数表示观众据称在魔术结束后会在自己的账户中看到的金额。板上也可以保留其他多余的数，只要所有需要的金额都已出现即可。

给定一个包含 $n$ 个数的数组 $x_1,x_2,\dots,x_n$，表示不同版本的魔术可能需要的最终金额。

制作人提出 $q$ 个询问。每个询问选择数组 $x$ 的一个子区间 $[l,r]$，并指定板上的初始金额 $S$。

对于每个询问，请判断：能否从板上唯一的数 $S$ 出发，通过上述操作，得到 $x_l,x_{l+1},\dots,x_r$ 这些数？这些数的顺序不重要，板上可以额外出现其他数。若区间内某个数出现多次，则板上也需要出现相应次数。如果可以，请求出所有拆分操作的最小总费用；否则，请报告无法完成这个魔术。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示数组长度和询问个数，满足 $1\le n,q\le 2\cdot10^5$。

第二行包含 $n$ 个整数 $x_1,x_2,\dots,x_n$，满足 $1\le x_i\le10^6$。

接下来 $q$ 行，每行包含三个整数 $l,r,S$，描述一个询问，满足 $1\le l\le r\le n$，$1\le S\le10^9$。

输出格式

对于每个询问，在单独一行输出制作人完成魔术需要支付的最小硬币数。如果无法得到要求的这些数，输出 $-1$。

5 6
1 2 3 4 5
2 4 10
1 3 6
3 5 10
1 5 20
2 2 5
2 2 2

35
11
-1
160
6
0