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

给定 $n$ 个杏子种子，Sam 总共执行 $n - 1$ 个步骤来对它们进行排序。对于从 1 到 $n - 1$ 的每个步骤 $k$： - 他比较第一个种子和第二个种子。如果第二个种子较小，则交换它们的位置。 - 然后他比较第二个种子和第三个种子。如果第三个种子较小，则交换它们的位置。 - 他继续此过程，直到比较第 $(n - k)$ 个种子和第 $(n - k + 1)$ 个种子，如果第 $(n - k + 1)$ 个种子较小，则交换它们的位置。

Sam 的朋友 Tom 很快意识到这就是著名的冒泡排序算法。为了向 Sam 展示该算法的低效性，Tom 决定问 Sam $q$ 个问题。一个问题表示为一个元组 $[s, e, m, l, r]$。对于给定的 $n$ 个种子序列，每个问题 $[s, e, m, l, r]$ 要求计算：在对初始序列中从位置 $s$ 到 $e$ 的子序列应用 Sam 方法的前 $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)。应用 Sam 方法的一步 ($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$ 的子序列应用 Sam 方法的前 $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