题目描述

我们可以把 Stara Planina 山脉表示为平面上的一列 $N$ 个山峰。山峰编号为 $1$ 到 $N$，第 $i$ 个山峰的坐标为 $(i,h_i)$，其中 $h_i$ 表示第 $i$ 个山峰的海拔。

保证 $h_1,h_2,\ldots,h_N$ 是 $1,2,\ldots,N$ 的一个排列。相邻山峰 $i$ 与 $i+1$ 之间用线段相连。

由于夜间行走，要到达山上的任意位置，必须至少有一个正在工作的手电筒。现在有 $K$ 个手电筒可以买。第 $j$ 个手电筒可以在山峰 $p_j$ 处以 $c_j$ 欧元购买，并且只在当前海拔属于区间 $[a_j,b_j]$ 时工作。

当海拔低于 $a_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$ 时没有任何手电筒工作。

对于每个 $1\le j\le K$，请判断：如果一开始位于山峰 $p_j$ 并购买手电筒 $j$，是否可以遍历整座山，即访问每个山峰至少一次。若可以，请求出总购买费用的最小值；该费用包含初始购买手电筒 $j$ 的费用。

输入格式

第一行包含两个正整数 $N,K$，表示山峰数量和可购买手电筒数量。

第二行包含 $N$ 个整数 $h_1,h_2,\ldots,h_N$。

接下来 $K$ 行，每行四个整数 $p_j,c_j,a_j,b_j$，表示手电筒 $j$ 可在山峰 $p_j$ 购买，价格为 $c_j$，工作海拔区间为 $[a_j,b_j]$。

输出格式

对每个 $j=1,2,\ldots,K$，输出一行：

• 如果从山峰 $p_j$ 开始并购买手电筒 $j$ 后，可以遍历整座山，则输出最小总费用；
• 如果不可能遍历整座山，或 $h_{p_j}\notin [a_j,b_j]$，输出 -1。

数据范围

• $1\le N,K\le 2000$
• $h_1,h_2,\ldots,h_N$ 是 $1$ 到 $N$ 的一个排列
• $1\le c_j\le 10^6$
• $1\le a_j\le b_j\le N$

子任务

只有通过某子任务及其所有依赖子任务的全部测试，才能获得该子任务分数。

样例

输入

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. 向左走到山峰 $1$；
2. 购买手电筒 $2$；
3. 向右走到山峰 $4$；
4. 购买手电筒 $3$；
5. 向右走到山峰 $7$。

此时已经访问所有山峰，花费为 $1+2+4=7$。

不能以手电筒 $2,6,7$ 作为初始手电筒，因为它们在出售处的海拔不工作。手电筒 $3,4$ 作为初始手电筒时无需再购买额外手电筒。手电筒 $5$ 作为初始手电筒时还需要之后购买手电筒 $4$。若以手电筒 $8$ 开始，会停留在山峰 $7$，即使在山峰 $7$ 买到手电筒，仍不能走到山峰 $6$。