Lanterns

Farmer John took his herd of cows on a hiking trip in the Alps. Night fell and the trip ended. But some cows are still stranded along the mountain range, and John must rescue all of them.

The mountain range is a series of $n$ points on a vertical 2D plane. We call these points peaks. The peaks are numbered from $1$ to $n$ in order. Peak $i$ has coordinates $(i, h_i)$, where $h_i$ is the altitude of peak $i$. The values $h_1, h_2, \dots, h_n$ form a permutation of $1$ through $n$. That is, for each $j = 1, \dots, n$, there is exactly one $i \in \{1, \dots, n\}$ with $h_i = j$.

For each $1 \le i < n$, peaks $i$ and $i+1$ are joined by a straight line segment.

Because it is night, John cannot walk anywhere unless he has at least one working lantern. There are $k$ lanterns for sale. Lantern $j$ can be bought at peak $p_j$ for $c_j$ francs. It works only when John's altitude is within $[a_j, b_j]$. If his altitude is strictly below $a_j$ or strictly above $b_j$, lantern $j$ does not work. Lanterns do not break when they leave their range. If John returns to an altitude within the range, the lantern works again.

If John is at peak $p$, he can do one of three things:

• Buy one of the lanterns available at peak $p$. Once bought, a lantern can be used forever.
• If $p > 1$, walk to peak $p-1$.
• If $p < n$, walk to peak $p+1$.

John must never move without a working lantern. He can walk between two adjacent peaks only if, at every moment of the walk, at least one lantern he already owns works. The lantern does not have to be the same one throughout the walk.

For example, suppose John is at a peak with altitude $4$ and wants to walk to an adjacent peak with altitude $1$. If he has lanterns working on $[1, 3]$ and $[3, 4]$, he can make the walk. If he has lanterns working only on $[1, 1]$ and $[2, 5]$, he cannot. No lantern works at altitude $1.47$, for instance.

For each $j$ with $a_j \le h_{p_j} \le b_j$, suppose John starts by buying lantern $j$ at peak $p_j$. He must then visit all $n$ peaks at least once using the three actions above. For each such $j$, find the minimum total number of francs he must spend to search the whole range. The cost includes the price of lantern $j$.

The first line contains $n$ and $k$ ($1 \le n \le 2000$, $1 \le k \le 2000$). The second line contains $h_1, h_2, \dots, h_n$ ($1 \le h_i \le n$), which is a permutation of $1$ through $n$.

Each of the next $k$ lines contains four integers $p_j$, $c_j$, $a_j$, and $b_j$ ($1 \le p_j \le n$, $1 \le c_j \le 10^6$, $1 \le a_j \le b_j \le n$). These are the peak where lantern $j$ can be bought, its cost, and the lower and upper bounds of its working altitude range.

For each $j$, print one line.

• If $h_{p_j}$ is outside $[a_j, b_j]$, print $-1$.
• Otherwise, if John cannot search the whole range after buying lantern $j$ first, print $-1$.
• Otherwise, print the minimum total cost for searching the whole range when John starts by buying lantern $j$.

If John starts by buying lantern $1$ at peak $3$, he can do the following:

• Walk left twice to peak $1$.
• Buy lantern $2$.
• Walk right to peak $4$.
• Buy lantern $3$.
• Walk right to peak $7$.

By then he has visited every peak and spent $1 + 2 + 4 = 7$ francs.

Lanterns $2$, $6$, and $7$ cannot be used as a starting purchase, because they do not work at the altitude of the peak where they are sold. Their answers are all $-1$.

If John starts with lantern $3$ or $4$, he can visit all peaks without buying anything else.

If John starts with lantern $5$, he must also buy lantern $4$ later.

If John starts with lantern $8$, he gets stuck at peak $7$. Even if he also buys lantern $7$, he still cannot walk from peak $7$ to peak $6$.