Lanterns

Farmer John took his herd of cows on a hiking trip in the Alps! As night fell, the trip had to end, and some cows got stranded across the mountain range. Now, John needs to rescue them all!

The mountain range can be represented as a series of $n$ points in a 2D plane, referred to as "vertices." These vertices are numbered from 1 to $n$. Vertex $i$ has coordinates $(i,h_i)$, where $h_i$ is the height of vertex $i$. The heights $h_1,h_2,\dots ,h_n$ form a permutation of the numbers from 1 to $n$. This means that for each $j=1,...,n$, there is exactly one $i$ such that $h_i=j$.

Each pair of consecutive vertices $i$ and $i+1$ ($1\le i<n$) is connected by a straight line segment.

Since it is nighttime, John cannot travel without at least one functioning lantern. Fortunately, there are $k$ lanterns available for purchase. For each $j$ ($1\le j\le k$), the $j$-th lantern can be bought at vertex $p_j$ for $c_j$ francs.

However, each lantern $j$ only works when John is at a height within the range $[a_j,b_j]$. If John's height is strictly less than $a_j$ or strictly greater than $b_j$, lantern $j$ will not function. Lanterns do not break when outside their range; they simply stop working and will function again once John returns to a valid height.

If John is at vertex $p$, he can perform one of the following actions:

- Buy one of the lanterns available at vertex $p$. Once purchased, a lantern can be used indefinitely. - Move to vertex $p-1$ if $p>1$. - Move to vertex $p+1$ if $p<n$.

John must always have a functioning lantern to move. He can only travel between two vertices if, at every point along the way, at least one of his purchased lanterns is working. It doesn't have to be the same lantern throughout the journey.

For example, if John is at a vertex with height 4 and wants to move to a neighboring vertex with height 1, he can do so if he has lanterns that work in the height ranges $[1,3]$ and $[3,4]$. However, if his lanterns work in the ranges $[1,1]$ and $[2,5]$, he cannot move between these vertices because no lantern will work at height 1.47.

Your task is to determine the answer for various independent queries.

For each $1\le j\le k$ such that $a_j\le h_{p_j}\le b_j$, assume John starts his journey from vertex $p_j$ by purchasing lantern $j$. To traverse the entire mountain range, he must visit each of the $n$ vertices at least once, using the operations described above. For each $j$, determine the minimum number of francs John needs to spend to traverse the entire mountain range, including the initial cost of purchasing lantern $j$.

Input

The first line contains $n$ and $k$ ($1\le n\le 2000$, $1\le k\le 2000$) — the number of vertices in the mountain range and the number of available lanterns, respectively.

The second line contains $n$ space-separated integers $h_1,h_2,\dots ,h_n$ ($1\le h_i\le n$): the heights of each vertex. It is guaranteed that the values $h_i$ form a permutation of numbers from 1 to $n$.

The next $k$ lines each contain four space-separated numbers $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$) — the vertex number where lantern $j$ can be purchased, its price, and its range, respectively.

Output

For each $j$ ($1\le j\le k$), output one line:

- If $h_{p_j}$ is outside the range $[a_j,b_j]$, output $-1$. - Otherwise, if John cannot traverse all the vertices starting by purchasing lantern $j$, output $-1$. - Otherwise, output the minimum number of francs John needs to spend to visit each vertex of the mountain range starting with lantern $j$.

Examples

Note

For example, if John starts by purchasing lantern 1 at vertex 3, he can:

- Move left twice to vertex 1 - Purchase lantern 2 - Move right to vertex 4 - Purchase lantern 3 - Move right to vertex 7

In this scenario, John visits each vertex at least once and spends a total of 1 + 2 + 4 = 7 francs.

John cannot start by purchasing lanterns 2, 6, or 7, as they do not work at the height where they can be purchased. Therefore, the answer for these lanterns is $-1$.

If John starts by purchasing lantern 3 or 4, he can visit all vertices without buying additional lanterns.

If John starts by purchasing lantern 5, he must also purchase lantern 4 later.

If John starts by purchasing lantern 8, he will get stuck at vertex 7. Even if he buys lantern 7, he still cannot move from vertex 7 to vertex 6.

Scoring

Block 1 (9 points): $n\le 20$ and $k\le 6$.

Block 2 (12 points): $n\le 70$ and $k\le 70$.

Block 3 (23 points): $n\le 300$, $k\le 300$ and $h_i=i$ for all $1\le i\le n$.

Block 4 (16 points): $n\le 300$, $k\le 300$.

Block 5 (40 points): no additional constraints.