Farmer John 带着他的牛群去阿尔卑斯山徒步旅行！过了一会儿，天黑了，徒步旅行结束了。然而，一些牛被困在了山脉各处，现在轮到 John 去营救它们了！
牛群目前正在穿越的山脉可以表示为垂直二维平面上的一系列顶点。我们将这些顶点称为“山峰”。山峰按顺序编号为 $1$ 到 $n$。山峰 $i$ 的坐标为 $(i, h_i)$。值 $h_i$ 表示山峰 $i$ 的海拔。保证 $h_1, h_2, \dots, h_n$ 是 $1 \dots n$ 的一个排列。（也就是说，对于每个 $j \in \{1, \dots, n\}$，恰好有一个 $i \in \{1, \dots, n\}$ 使得 $h_i = j$。）
对于每个 $i$ ($1 \le i < n$)，山峰 $i$ 和 $i+1$ 由一条直线段连接。
由于是夜晚，除非 John 随身携带至少一个功能正常的灯笼，否则他不能前往山脉的任何部分。幸运的是，有 $k$ 个灯笼可供购买。对于每个 $j$ ($1 \le j \le k$)，灯笼 $j$ 可以在山峰 $p_j$ 以 $c_j$ 法郎的价格购买。
不幸的是，灯笼 $j$ 仅在 John 当前的海拔处于范围 $[a_j, b_j]$ 内时才有效。换句话说，每当 John 当前的海拔严格小于 $a_j$ 或严格大于 $b_j$ 时，灯笼 $j$ 就不工作。注意，灯笼在离开其工作范围时不会损坏。例如，当 John 的海拔超过 $b_j$ 时，灯笼 $j$ 将停止工作，但只要 John 回到海拔 $b_j$，灯笼就会再次开始工作。
如果 John 目前在山峰 $p$，他可以执行以下三种动作之一： 他可以购买在山峰 $p$ 可用的灯笼之一。一旦他购买了一个灯笼，他就可以永远使用它。 如果 $p > 1$，他可以走到山峰 $p - 1$。 * 如果 $p < n$，他可以走到山峰 $p + 1$。
John 在移动时必须始终拥有一个工作的灯笼。他只能在相邻的山峰之间行走，前提是在行走的每一刻，他已经拥有的灯笼中至少有一个是工作的。（在整个行走过程中，不需要是同一个灯笼。）
例如，假设 Farmer John 目前位于海拔为 $4$ 的山峰，并希望走到海拔为 $1$ 的相邻山峰。如果 John 拥有的灯笼在海拔范围 $[1, 3]$ 和 $[3, 4]$ 内有效，这将允许他从一个山峰走到另一个山峰。
然而，如果 John 拥有的灯笼仅在范围 $[1, 1]$ 和 $[2, 5]$ 内有效，那么 John 暂时还无法在这两个山峰之间行走：例如，他的灯笼在海拔 $1.47$ 时都不工作。
你的任务是确定多个独立问题的答案。
对于每个满足 $1 \le j \le k$ 且 $a_j \le h_{p_j} \le b_j$ 的 $j$，假设 John 通过购买灯笼 $j$ 开始他的搜索，位于山峰 $p_j$。为了搜索整个山脉，他必须通过重复执行上述三种动作中的一种，至少访问每一个山峰一次。对于这些 $j$ 中的每一个，确定 John 为了搜索整个山脉需要花费的法郎总数（最小值）。（此成本包括最初购买灯笼 $j$ 的费用。）
输入格式
第一行包含 $n$ 和 $k$ ($1 \le n \le 2000, 1 \le k \le 2000$) —— 分别是山峰的数量和可用灯笼的数量。
第二行包含 $n$ 个空格分隔的整数 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le n$)：每座山峰的海拔。保证 $h_i$ 的值是 $1$ 到 $n$ 的一个排列。
接下来的 $k$ 行中，第 $j$ 行包含四个空格分隔的整数 $p_j, c_j, a_j$ 和 $b_j$ ($1 \le p_j \le n, 1 \le c_j \le 10^6, 1 \le a_j \le b_j \le n$) —— 分别是灯笼 $j$ 可以购买的山峰、其价格和工作范围。
输出格式
对于每个 $j$ ($1 \le j \le k$)，输出一行： 如果 $h_{p_j}$ 在范围 $[a_j, b_j]$ 之外，输出 $-1$。 否则，如果 John 无法通过首先购买灯笼 $j$ 来搜索整个山脉，输出 $-1$。 * 否则，输出 John 如果以购买灯笼 $j$ 开始，为了搜索整个山脉需要花费的法郎总数（最小值）。
子任务
- 子任务 1 (9 分): $n \le 20$ 且 $k \le 6$。
- 子任务 2 (12 分): $n \le 70$ 且 $k \le 70$。
- 子任务 3 (23 分): $n \le 300, k \le 300$ 且对于所有 $1 \le i \le n$，$h_i = i$。
- 子任务 4 (16 分): $n \le 300, k \le 300$。
- 子任务 5 (40 分): 无附加限制。
样例
样例输入 1
7 8 4 2 3 1 5 6 7 3 1 2 4 1 2 1 3 4 4 1 7 6 10 1 7 6 20 6 6 6 30 5 5 7 40 1 6 7 50 7 7
样例输出 1
7 -1 4 10 30 -1 -1 -1
说明
如果 John 从在山峰 $3$ 购买灯笼 $1$ 开始，他可以执行以下动作序列： 向左走两次到达山峰 $1$ 购买灯笼 $2$ 向右走到达山峰 $4$ 购买灯笼 $3$ * 向右走到达山峰 $7$
此时，John 已经至少访问了每个山峰一次，并且他总共花费了 $1 + 2 + 4 = 7$ 法郎。
John 不能从购买灯笼 $2, 6$ 或 $7$ 开始，因为它们在购买它们的海拔处不工作。因此，这些灯笼的答案均为 $-1$。
如果 John 从购买灯笼 $3$ 或 $4$ 开始，他可以访问所有山峰而无需购买额外的灯笼。
如果 John 从购买灯笼 $5$ 开始，他稍后还必须购买灯笼 $4$。
如果 John 从购买灯笼 $8$ 开始，他将被困在山峰 $7$。即使他也购买了灯笼 $7$，他仍然无法从山峰 $7$ 走到山峰 $6$。