题目描述

信心花舍里从左到右一次陈列着 $n$ 盆花，其中第 $i$ 盆有美丽值 $a_i$。 花舍的主人可可能会对花进行调整。在一次调整中：小可可会先比较第一盆和第二盆花的美丽值，如果第一盆比第二盆美丽，就会交换第一和第二盆；然后比较和交换第二、第三盆花（此时的第二盆花可能是原先的第一盆花）；这样一直比较交换下去，直到对第 $n-1$ 盆、第 $n$ 盆花进行完比较交换。熟悉算法的你一定可以看出，这个的本质就是冒泡排序。 小可可想要把好的花送给别人，而把不那么美丽的花留给自己。所以他想知道，如果他对花进行了 $c$ 次调整，那么在调整后的第 $l$ 到 $r$ 盆花中，前 $k$ 小的美丽值之和是多少。 小可可不算是个专注的人，所以他会向你提问 $q$ 次，但却从未实际对花进行调整。

输入格式

第一行两个正整数 $n$ 和 $q$。 接下来一行 $n$ 个正整数，表示每朵花的美丽值。 接下来 $q$ 行，每行四个整数 $c, l, r, k$，表示一次提问。

输出格式

输出 $q$ 行，表示对每次小可可提问的回答。

样例 1 输入

6 10 3 6 5 2 1 3 1 3 5 3 1 3 5 3 3 1 6 2 3 2 4 3 3 2 5 3 0 2 4 1 1 2 6 1 2 5 5 1 1 2 5 4 1 3 5 3

样例 1 输出

6 6 3 7 7 2 1 5 11 6

数据规模与约定

对于所有 20 个测试点，有 $1 \leq n, q \leq 5 \times 10^5$, $1 \leq a_i \leq n$, $0 \leq c < n$, $1 \leq l \leq r \leq n$, $1 \leq k \leq r - l + 1$; 对于测试点 1, $1 \leq n, q \leq 500$; 对于测试点 2, $1 \leq n, q \leq 3000$; 对于测试点 3 $\sim$ 4, $1 \leq n, q \leq 10^5$, $0 \leq c < 5$; 对于测试点 5 $\sim$ 9, $1 \leq a_i \leq 2$; 对于测试点 10 $\sim$ 13, $1 \leq n, q \leq 10^5$; 对于测试点 14 $\sim$ 16, $1 \leq k \leq 5$; 对于测试点 17 $\sim$ 20, 无特殊限制。