Jill 有一些珠宝，她想根据大小将它们按非递减顺序排序。她使用了一种独特的方法来对珠宝进行排序，描述如下：

给定 $n$ 个珠宝，Jill 总共执行 $n-1$ 个步骤来对它们进行排序。对于每个步骤 $k$（从 $1$ 到 $n-1$）：

• 她比较第一个珠宝和第二个珠宝。如果第二个珠宝较小，她就交换它们的位置。
• 然后她比较第二个珠宝和第三个珠宝。如果第三个珠宝较小，她就交换它们的位置。
• 她继续这个过程，直到比较第 $(n-k)$ 个珠宝和第 $(n-k+1)$ 个珠宝，如果第 $(n-k+1)$ 个珠宝较小，则交换它们的位置。

Jill 的朋友 Jessie 很快意识到这就是著名的冒泡排序算法。为了向 Jill 展示该算法的低效性，Jessie 决定问 Jill $q$ 个问题。一个问题由一个元组 $[s, e, m, l, r]$ 表示。对于给定的 $n$ 个珠宝序列，每个问题 $[s, e, m, l, r]$ 要求计算：在对初始序列中从位置 $s$ 到 $e$ 的珠宝子序列应用 Jill 方法的前 $m$ 个步骤后，该（部分）排序子序列中从位置 $l$ 到 $r$ 的珠宝大小之和。

例如，考虑四个 ($n=4$) 珠宝，大小为 $(1, 3, 4, 2)$，以及两个 ($q=2$) 问题：$[2, 4, 1, 2, 2]$ 和 $[1, 4, 2, 3, 4]$。

对于第一个问题，从第二个 ($s=2$) 珠宝到第四个 ($e=4$) 珠宝的子序列大小为 $(3, 4, 2)$。应用 Jill 方法的一步 ($m=1$) 后，它变为 $(3, 2, 4)$。在这个（部分）排序子序列中，从第二个位置 ($l=2$) 到第二个位置 ($r=2$) 的珠宝大小之和为 $2$。

对于第二个问题，子序列为 $(1, 3, 4, 2)$。应用两步后，它变为 $(1, 2, 3, 4)$。在这个（部分）排序序列中，从位置 $3$ 到位置 $4$ 的珠宝大小之和为 $3+4=7$。

给定一个包含 $n$ 个珠宝的序列和 $q$ 个问题，编写一个程序来计算每个问题的答案。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 1\,000\,000$, $1 \le q \le 500\,000$)，其中 $n$ 表示珠宝的数量，$q$ 表示问题的数量。

第二行包含 $n$ 个整数，由空格分隔，表示珠宝的初始大小。每个大小在 $1$ 到 $10^9$ 之间（含边界）。

接下来的 $q$ 行，每行包含五个正整数 $s, e, m, l, r$，表示一个查询 $[s, e, m, l, r]$，由空格分隔，其中 $1 \le s < e \le n$，$1 \le m \le e-s$，$1 \le l \le r \le e-s+1$。

输出格式

对于每个问题，输出一行答案。问题 $[s, e, m, l, r]$ 的答案是：在对输入序列中从位置 $s$ 到 $e$ 的珠宝子序列应用 Jill 方法的前 $m$ 个步骤后，该（部分）排序子序列中从位置 $l$ 到 $r$ 的珠宝大小之和。

样例

样例输入 1

4 2
1 3 4 2
2 4 1 2 2
1 4 2 3 4

样例输出 1

2
7

样例输入 2

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

样例输出 2

1
5
3

样例输入 3

6 2
5 4 5 1 1 4
3 6 1 1 3
1 6 1 1 4

样例输出 3

6
11