现在给出 $q$ 个询问，每个询问包含整数 $k$、$l$ 和 $r$。对于每个询问，请计算 $f(k,a,l,r)$。

输入格式

第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($1 \leq n \leq 10^5$，$1 \leq q \leq 5\cdot 10^4$)。

接下来一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($2 \leq a_i \leq 10^5$)。

接下来的 $q$ 行，每行包含三个整数 $k$、$l$ 和 $r$ ($1 \leq k \leq 10^5$，$1 \leq l \leq r \leq n$)。

保证所有测试用例的 $n$ 之和不超过 $10^5$，所有测试用例的 $q$ 之和不超过 $5\cdot 10^4$。

输出格式

对于每个询问，输出一行答案。

2
5 3
2 3 5 7 11
2 1 5
2 2 4
2310 1 5
4 3
18 12 8 9
216 1 2
48 2 4
82944 1 4

5
6
1629
13
12
520