{"raw_statement":[{"iden":"background","content":"Day 1 Problem D.\n\n题面译自 [EGOI2021 lantern](https://stats.egoi.org/media/task_description/2021_lantern_en.pdf)。"},{"iden":"statement","content":"农夫约翰带着他的奶牛群在阿尔卑斯山进行了一次徒步旅行！一段时间后，天色转暗，旅行结束了。然而，一些奶牛仍然被困在山脉的各个地方，现在约翰需要营救它们！\n\n现在牛群正在穿越的山脉用平面直角坐标系中的 $n$ 个点表示。我们称这些点为“山峰”。山峰被依次编号为 $1\\sim n$。第 $i$ 座山峰的坐标为 $(i,h_i)$。值 $h_i$ 代表第 $i$ 座山峰的**海拔高度**。保证 $h_1,h_2,\\ldots h_n$ 构成一个 $1\\sim n$ 的排列。\n\n山峰 $i$ 和山峰 $i+1$ 用一条线段相连。\n\n由于现在是晚上，约翰必须携带至少一盏正常工作的灯笼才能上山。幸运的是，有 $k$ 个灯笼可供购买。第 $j$ 个灯笼可以在山峰 $p_j$ 以 $c_j$ 法郎的价格购买。\n\n不幸的是，第 $j$ 个灯笼只有在约翰的海拔在 $[a_j,b_j]$ 时才能正常工作。换句话说，如果约翰的海拔严格低于 $a_j$ 或严格高于 $b_j$，第 $j$ 个灯笼不会正常工作。需要注意的是，灯笼在离开海拔范围时不会损坏。例如，当约翰的海拔超过 $b_j$ 时，第 $j$ 个灯笼会停止工作，但只要约翰返回到海拔 $b_j$，灯笼会重新开始工作。\n\n如果约翰现在在山峰 $p$，他可以执行以下三种操作之一：\n\n- 他可以买一个在 $p$ 处售卖的灯笼。购买灯笼后，他可以永久使用。\n- 如果 $p > 1$，他可以走到山峰 $p-1$。\n- 如果 $p < n$，他可以走到山峰 $p+1$。\n\n约翰在没有正常工作的灯笼时不能移动。他必须保证每个时刻都有至少一盏灯笼正常工作，才能在两座山峰间移动。（在行走过程中不必是同一盏灯笼。）\n\n例如，假设农夫约翰目前在海拔为 $4$ 的山峰上，希望走到高度为 $1$ 的相邻山峰。如果约翰有海拔范围为 $[1,3]$ 和 $[3,4]$ 的两盏灯笼，他可以从一个山峰走到另一个山峰。\n\n但是，如果约翰只有海拔范围为 $[1,1]$ 和 $[2,5]$ 的两盏灯笼，他无法在这两座山峰间行走：例如，他没有灯笼能在海拔 $1.47$ 处正常工作。\n\n你需要给出多个独立问题的答案。\n\n对于每个满足 $a_j\\le h_{p_j}\\le b_j$ 的 $1\\le j\\le k$，假设约翰一开始在山峰 $p_j$ 并买下第 $j$ 个灯笼。为了搜索整个山脉，他必须重复执行上面提到的三种操作。对于每个 $j$，求出约翰至少需要花几法郎，才能搜索整个山脉。（这个花费包括初始时买的第 $j$ 个灯笼。）"},{"iden":"input","content":"第一行两个整数 $n,k$——山峰个数和灯笼个数。\n\n第二行 $n$ 个整数 $h_1,h_2,\\ldots,h_n$：每座山峰的海拔。保证 $h_i$ 构成一个 $1\\sim n$ 的排列。\n\n接下来 $k$ 行，每行四个整数 $p_j,c_j,a_j,b_j$——第 $j$ 个灯笼的售卖位置、价格和海拔范围。"},{"iden":"output","content":"对于每个 $1\\le j\\le k$，输出一行：\n\n- 若 $h_{p_j}$ 不在 $[a_j,b_j]$ 内，输出 $-1$。\n- 否则，如果约翰一开始购买第 $j$ 个灯笼，无法搜索整个山脉，输出 $-1$。\n- 否则，输出此时的最少花费。"},{"iden":"note","content":"**样例解释**\n\n如果约翰从第 $3$ 座山峰开始，购买第 $1$ 个灯笼，他可以如下操作：\n\n- 向左走两次，到达山峰 $1$。\n- 购买灯笼 $2$。\n- 向右走到山峰 $4$。\n- 购买灯笼 $3$。\n- 向右走到山峰 $7$。\n\n此时，约翰到达了每座山峰至少一次，花费了 $1+2+4=7$ 法郎。\n\n约翰不能从购买灯笼 $2,6,7$ 开始，因为它们在购买的海拔处不工作。因此，它们的答案为 $-1$。\n\n如果约翰从购买灯笼 $3,4$ 开始，他不用购买其他灯笼就可以访问每座山峰。\n\n如果约翰从购买灯笼 $5$ 开始，他必须购买灯笼 $4$。\n\n如果约翰从购买灯笼 $8$ 开始，他会被困在山峰 $7$。即使他购买了灯笼 $7$，他依然无法从山峰 $7$ 走到山峰 $6$。\n\n---\n\n**数据范围**\n\n对于全部数据，$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$。\n\n- 子任务一（$9$ 分）：$n\\le 20$，$k\\le 6$。\n- 子任务二（$12$ 分）：$n,k\\le 70$。\n- 子任务三（$23$ 分）：$n,k\\le 300$，$h_i=i$。\n- 子任务四（$16$ 分）：$n,k\\le 300$。\n- 子任务五（$40$ 分）：无特殊限制。"}],"translated_statement":null,"sample_group":[["7 8\n4 2 3 1 5 6 7\n3 1 2 4\n1 2 1 3\n4 4 1 7\n6 10 1 7\n6 20 6 6\n6 30 5 5\n7 40 1 6\n7 50 7 7","7\n-1\n4\n10\n30\n-1\n-1\n-1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}