题目描述

题目译自 European Girls' Olympiad in Informatics 2021 Day1 T4. Lanterns

农夫约翰带着他的牛群去阿尔卑斯山远足！天色渐晚，远足活动结束了。然而，一些牛仍然被困在山脉各处，约翰必须把它们全部救回来！

牛群所在的山脉可以表示为二维垂直平面上的 $n$ 个顶点，我们称之为山峰。这些山峰按顺序编号为 $1$ 到 $n$。山峰 $i$ 的坐标为 $\left(i, h_i\right)$，其中 $h_i$ 表示山峰 $i$ 的海拔。保证 $h_1, h_2, \ldots, h_n$ 是 $1$ 到 $n$ 的一个排列。（即，对于每个 $j=1, \ldots, n$，恰好有一个 $i \in \{1, \ldots, n\}$ 满足 $h_i = j$。）

对于每个 $i$ $(1 \leq i < n)$，山峰 $i$ 和 $i+1$ 之间通过一条直线段连接。

由于是夜晚，约翰除非携带至少一个能用的灯笼，否则无法在山脉中移动。幸运的是，有 $k$ 个灯笼可供购买。对于每个 $j$ $(1 \leq j \leq k)$，灯笼 $j$ 可以在山峰 $p_j$ 以 $c_j$ 法郎的价格购买。

但灯笼 $j$ 只有当约翰当前海拔在 $\left[a_j, b_j\right]$ 范围内时才有效。换句话说，当约翰的海拔严格小于 $a_j$ 或严格大于 $b_j$ 时，灯笼 $j$ 无法工作。注意，灯笼离开其有效范围不会损坏。例如，当约翰的海拔超过 $b_j$ 时，灯笼 $j$ 会停止工作，但一旦回到 $b_j$ 或以下，灯笼又会恢复正常。

如果约翰当前在山峰 $p$，他可以执行以下三种操作之一：

• 购买山峰 $p$ 上可用的一个灯笼。购买后，灯笼可永久使用。
• 如果 $p > 1$，他可以步行到山峰 $p-1$。
• 如果 $p < n$，他可以步行到山峰 $p+1$。

约翰绝不能在没有有效灯笼的情况下移动。只有当他全程至少有一个已拥有的灯笼有效时，他才能在相邻山峰间步行。（整个步行过程中不必始终是同一个灯笼有效。）

例如，假设约翰当前位于海拔 $4$ 的山峰，想步行到海拔 $1$ 的相邻山峰。如果他有有效范围为 $[1,3]$ 和 $[3,4]$ 的灯笼，他就可以完成这段步行。

但如果他的灯笼有效范围仅为 $[1,1]$ 和 $[2,5]$，他暂时无法步行到目标山峰：例如，在海拔 $1.47$ 时，他的灯笼都无法工作。

你的任务是回答多个独立的问题。对于每个满足 $a_j \leq h_{p_j} \leq b_j$ 的 $j$ $(1 \leq j \leq k)$，假设约翰从山峰 $p_j$ 开始，购买灯笼 $j$。为了搜索整个山脉，他必须通过重复上述三种操作，至少访问每个山峰一次。对于每个这样的 $j$，计算约翰搜索整个山脉所需的最小总法郎数。（此费用包括初始购买灯笼 $j$ 的费用。）

输入格式

第一行包含 $n$ 和 $k$ $(1 \leq n \leq 2000, 1 \leq k \leq 2000)$，分别表示山峰数量和可购买的灯笼数量。

第二行包含 $n$ 个用空格分隔的整数 $h_1, h_2, \ldots, h_n$ $(1 \leq h_i \leq n)$，表示每个山峰的海拔。保证 $h_i$ 是 $1$ 到 $n$ 的一个排列。

接下来的 $k$ 行，每行包含四个用空格分隔的整数 $p_j, c_j, a_j, b_j$ $(1 \leq p_j \leq n, 1 \leq c_j \leq 10^6, 1 \leq a_j \leq b_j \leq n)$，分别表示可购买灯笼 $j$ 的山峰、其费用及其有效海拔范围。

输出格式

对于每个 $j$ $(1 \leq j \leq k)$，输出一行：

• 如果 $h_{p_j}$ 不在 $\left[a_j, b_j\right]$ 范围内，输出 $-1$。
• 如果约翰从购买灯笼 $j$ 开始无法搜索整个山脉，输出 $-1$。
• 否则，输出约翰从购买灯笼 $j$ 开始搜索整个山脉所需的最小总法郎数。

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

7
-1
4
10
30
-1
-1
-1

如果约翰从山峰 $3$ 购买灯笼 $1$ 开始，他可以按以下顺序操作：

• 向左步行两次到山峰 $1$。
• 购买灯笼 $2$。
• 向右步行到山峰 $4$。
• 购买灯笼 $3$。
• 向右步行到山峰 $7$。

此时，约翰已经至少访问了每个山峰一次，总共花费 $1+2+4=7$ 法郎。

约翰无法从购买灯笼 $2$、$6$ 或 $7$ 开始，因为这些灯笼在其购买地点的海拔下无法工作。因此，这些灯笼的答案为 $-1$。

如果约翰从购买灯笼 $3$ 或 $4$ 开始，他无需购买其他灯笼即可访问所有山峰。

如果约翰从购买灯笼 $5$ 开始，他必须稍后购买灯笼 $4$。

如果约翰从购买灯笼 $8$ 开始，他会被困在山峰 $7$。即使他再购买灯笼 $7$，他仍然无法从山峰 $7$ 步行到山峰 $6$。

数据范围与提示

详细子任务附加限制及分值如下表所示。