You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

爬山（$\texttt{climb}$）

【题目描述】

露娜和朝日喜欢爬山。

这一天她们来到了一片山脉，山脉由 $n$ 个山峰组成，山脉可以看做平面直角坐标系，其中第 $i$ 座山峰的坐标为 $(i,h_i)$。

相邻的两座山峰之间有道路，道路就是连接 $(i,h_i)$ 和 $(i+1,h_{i+1})$ 的一条线段。

由于现在天色已晚，她们必须带着至少一盏在照明的手电筒才能上山。

但现在她们手上并没有手电筒，但幸运的是，山脉中有 $m$ 家手电筒商店，第 $i$ 家商店在第 $p_i$ 座山峰上，以 $c_i$ 的价格出售一个手电筒，但这个手电筒可能有问题，它只能在海拔为 $[l_i,r_i]$ 的范围内才能照明，即当且仅当当前的纵坐标在 $[l_i,r_i]$ 之间时，这个手电筒才能照明。

假如露娜和朝日当前在山峰 $u$，那么她们可以执行以下三种操作之一：

• 去某个 $u$ 处的商店购买手电筒。
• 沿着山峰间的道路前往第 $u-1$ 座山峰（$u>1$）。
• 沿着山峰间的道路前往第 $u+1$ 座山峰（$u<n$）。

注意，当她们在某两座山峰间移动时，她们必须保证过程中每个时刻都至少有一个手电筒在照亮（可以不是同一个手电筒）。

例如，假如她们要从 $(1,5)$ 前往 $(2,1)$，她们现有的手电筒的工作范围分别是 $[1,3],[3,5]$，那么她们可以抵达 $(2,1)$，但如果她们现有的手电筒的工作范围是 $[1,2],[3,5]$，她们是不能到达 $(2,1)$ 的，因为在 $(1.625,2.5)$ 这个位置时，她们会被黑暗吞没。

显然，她们必须至少买一个手电筒，所以露娜想知道，对于每个 $i=1,2,\dots,m$，假如她们从 $p_i$ 开始，并在一开始就买下这座商店出售的手电筒，那么她们游历 $n$ 座山峰至少一次最小代价是多少？

• 假如对于某个 $i$，$h_{p_i}\not\in[l_i,r_i]$，那么她们显然立即会被黑暗吞没，请输出 $-1$。
• 如果她们从 $p_i$ 出发无论如何也无法遍历所有山峰，请输出 $-1$。
• 否则输出买手电筒的最小花费（包括初始的第 $i$ 个手电筒）。

【输入格式】

从 $\texttt{climb.in}$ 中读入数据。

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示 $h_1,h_2,\dots,h_n$。

接下来 $m$ 行，每行四个整数，$p_i,c_i,l_i,r_i$ 表示一个手电筒商店。

【输出格式】

输出到 $\texttt{climb.out}$ 中。

输出 $m$ 行，第 $i$ 行表示从第 $i$ 个商店出发遍历整个山脉的最小代价，无法遍历输出 $-1$。

【样例 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

【数据范围】

对于所有测试数据：$1\le n,m\le 2\times 10^3$，$h_1,h_2,\dots,h_n$ 构成一个 $1,2,\dots,n$ 的排列，$1\le c_i\le 10^6$。