定义冒泡排序的过程为：

对于一个长为 $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$。