定义冒泡排序的过程为：
对于一个长为 $n$ 的序列 $a_1,\dots,a_n$，进行 $n-1$ 轮“冒泡”操作，每次“冒泡”操作中进行以下操作：
- 如果 $a_1>a_2$ 则交换 $a_1,a_2$。
- 如果 $a_2>a_3$ 则交换 $a_2,a_3$。
- $\dots$
- 如果 $a_{n-1}>a_{n}$ 则交换 $a_{n-1},a_{n}$。
进行一轮“冒泡”操作的伪代码如下：
for i = 1 to n-1:
if a[i] > a[i + 1]:
swap(a[i], a[i + 1])给定一个数组 $b_1,b_2,\dots,b_n$。
每次询问 $(l,r,k,x,y)$，小 C 截取了 $b$ 数组的子区间 $[l,r]$，得到一个新的 $a$ 数组 $[a_1,\dots,a_{r-l+1}] = [b_l,\dots,b_r]$，并对 $a$ 数组进行了 $k$ 次“冒泡”操作。
你需要求出在 $k$ 次“冒泡”操作后，$\sum_{i=x}^y a_i$ 的值。
输入格式
第一行一个整数 $id$ 表示子任务编号。特别的，对于样例输入 $1$，有 $id=0$。
第二行两个整数 $n,q$。
接下来一行 $n$ 个整数 $b_1,\dots,b_n$。
接下来 $q$ 行每行 $5$ 个整数 $l,r,k,x,y$。
输出格式
输出 $q$ 行，每行一个整数表示答案。
输入输出样例
样例输入 1
0 4 2 1 3 4 2 2 4 1 2 2 1 4 2 3 4
样例输出 1
2 7
其余样例
下发文件中共有 $8$ 个样例，分别来自 $8$ 个子任务。
数据范围
对于所有数据：
- $1\le n \le 10^6$，$ 1\le q\le 5\times 10^5$
- $0\le b_i\le 10^9$，$1\le l < r\le n$，$1\le k\le r-l$，$1\le x\le y\le r-l+1$。
| 子任务编号 | $n,q$ 范围 | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $n \le 10, q \le 5000$ | 无 | $8$ |
| $2$ | $n\le 2\times 10^5, q\le 5$ | 无 | $14$ |
| $3$ | $n,q\le 2\times 10^5$ | $x=1,y=r-l+1-k$ | $10$ |
| $4$ | $n,q\le 2\times 10^5$ | $l=1,r=n$ | $12$ |
| $5$ | $n,q\le 2\times 10^5$ | $k\le 10$ | $14$ |
| $6$ | $n,q\le 2\times 10^5$ | $a_i\le 10$ | $16$ |
| $7$ | $n,q\le 2\times 10^5$ | 无 | $16$ |
| $8$ | $n \le 10^6,q\le 5\times 10^5$ | 无 | $10$ |