一家研究机构拥有两栋建筑，左实验室（Left Lab）和右实验室（Right Lab），由一条安全走廊连接。起初，所有被选中的员工都站在左实验室。

• 走廊一次最多容纳两人。
• 只有一枚安全徽章，每次穿过走廊（无论是单人还是两人同行）都必须携带该徽章。
• 如果两人同行，他们必须并肩行走，穿过时间等于两人中较慢者的用时。
• 如果从左实验室穿行到右实验室后，左实验室仍有员工，则右实验室必须有人将徽章带回左实验室，才能开始下一次从左到右的穿行。

为了观察策略如何影响总时间，考虑四名员工，其个人穿行时间分别为 $\{1, 2, 5, 10\}$。一种可能的策略如下：如果 $(1, 2)$ 先穿行（耗时 2 分钟），然后 $(1)$ 带徽章返回（1 分钟），接着 $(1, 5)$ 穿行（5 分钟），$(1)$ 返回（1 分钟），最后 $(1, 10)$ 穿行（10 分钟），总时间为 19 分钟。然而，存在另一种（更优的）策略：如果 $(1, 2)$ 先穿行（2 分钟），$(1)$ 返回（1 分钟），然后 $(5, 10)$ 一起穿行（10 分钟），$(2)$ 返回（2 分钟），最后 $(1, 2)$ 再次穿行（2 分钟），总时间变为 17 分钟，这比第一种策略的总穿行时间更短。为方便起见，这两种穿行序列总结在下表 1 和表 2 中。

表 1. 序列 A（总计 19 分钟）

表 2. 序列 B（总计 17 分钟）

给定 $n$ 名员工。员工 $i$ 穿过走廊需要 $T_i$ 分钟。同时给定 $q$ 个查询。每个查询由以下内容指定：

• 索引范围 $[x, y]$（包含边界），
• 时间范围 $[a, b]$（包含边界），以及
• 选择上限 $K$（你可以选择的最大员工人数）。

对于每个查询，考虑所有索引在 $[x, y]$ 范围内且穿行时间在 $[a, b]$ 范围内的员工。在这些员工中，选择穿行时间最短的 $K$ 名员工。如果符合条件的员工少于 $K$ 名，则全部选中。这些被选中的员工起初都带着唯一的徽章在左实验室。根据上述规则，计算所有被选中的员工到达右实验室所需的最短总穿行时间。如果没有选中任何员工，答案应为零。

给定 $n$ 名员工的穿行时间 $T_1, \dots, T_n$ 以及 $q$ 个形式为 $(x, y, a, b, K)$ 的查询，编写一个程序处理这些查询，并为每个查询输出被选中的员工到达右实验室的最短总穿行时间。

输入格式

程序从标准输入读取数据。输入的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 100,000$)，其中 $n$ 是员工人数，$q$ 是查询次数。员工编号从 1 到 $n$。第二行包含 $n$ 个整数 $T_1, \dots, T_n$ ($1 \le T_i \le 10^9$)，其中 $T_i$ 是员工 $i$ 的穿行时间 ($1 \le i \le n$)。接下来的 $q$ 行，每行包含五个整数 $x, y, a, b, K$，含义如上所述，其中 $1 \le x \le y \le n$；$1 \le a \le b \le 10^9$；$1 \le K \le n$。

输出格式

程序向标准输出写入数据。对于每个查询，输出一行，包含被选中的员工从左实验室移动到右实验室所需的最短总穿行时间。如果没有选中任何员工，输出 0。

样例

样例输入 1

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

样例输出 1

6
2
0

样例输入 2

4 4
5 1 10 2
1 4 1 10 4
1 4 2 10 2
1 4 2 10 4
1 3 1 13 3

样例输出 2

17
5
17
16