题目背景

Day 1 Problem D.

题面译自 EGOI2021 lantern。

题目描述

农夫约翰带着他的奶牛群在阿尔卑斯山进行了一次徒步旅行！一段时间后，天色转暗，旅行结束了。然而，一些奶牛仍然被困在山脉的各个地方，现在约翰需要营救它们！

现在牛群正在穿越的山脉用平面直角坐标系中的 $n$ 个点表示。我们称这些点为“山峰”。山峰被依次编号为 $1\sim n$。第 $i$ 座山峰的坐标为 $(i,h_i)$。值 $h_i$ 代表第 $i$ 座山峰的海拔高度。保证 $h_1,h_2,\ldots h_n$ 构成一个 $1\sim n$ 的排列。

山峰 $i$ 和山峰 $i+1$ 用一条线段相连。

由于现在是晚上，约翰必须携带至少一盏正常工作的灯笼才能上山。幸运的是，有 $k$ 个灯笼可供购买。第 $j$ 个灯笼可以在山峰 $p_j$ 以 $c_j$ 法郎的价格购买。

不幸的是，第 $j$ 个灯笼只有在约翰的海拔在 $[a_j,b_j]$ 时才能正常工作。换句话说，如果约翰的海拔严格低于 $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\le h_{p_j}\le b_j$ 的 $1\le j\le k$，假设约翰一开始在山峰 $p_j$ 并买下第 $j$ 个灯笼。为了搜索整个山脉，他必须重复执行上面提到的三种操作。对于每个 $j$，求出约翰至少需要花几法郎，才能搜索整个山脉。（这个花费包括初始时买的第 $j$ 个灯笼。）

输入格式

第一行两个整数 $n,k$——山峰个数和灯笼个数。

第二行 $n$ 个整数 $h_1,h_2,\ldots,h_n$：每座山峰的海拔。保证 $h_i$ 构成一个 $1\sim n$ 的排列。

接下来 $k$ 行，每行四个整数 $p_j,c_j,a_j,b_j$——第 $j$ 个灯笼的售卖位置、价格和海拔范围。

输出格式

对于每个 $1\le j\le k$，输出一行：

• 若 $h_{p_j}$ 不在 $[a_j,b_j]$ 内，输出 $-1$。
• 否则，如果约翰一开始购买第 $j$ 个灯笼，无法搜索整个山脉，输出 $-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

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$。

---

数据范围

对于全部数据，$1\le n,k\le 2\times 10^3$，$1\le h_i\le n$ 且 $h_i$ 构成一个 $1\sim n$ 的排列，$1\le p_j\le n$，$1\le c_j\le 10^6$，$1\le a_j\le b_j\le n$。

• 子任务一（$9$ 分）：$n\le 20$，$k\le 6$。
• 子任务二（$12$ 分）：$n,k\le 70$。
• 子任务三（$23$ 分）：$n,k\le 300$，$h_i=i$。
• 子任务四（$16$ 分）：$n,k\le 300$。
• 子任务五（$40$ 分）：无特殊限制。