Rescuing the Cows in the Alpines

Farmer John is rescuing his cows stranded across the Alpine mountains. The mountains are represented by n peaks on the plane with coordinates \((i,h_i)\) for \(i=1,2,\dots,n\). Here, \(h_1, h_2, \dots, h_n\) is a permutation of \(\{1,2,\dots,n\}\). Adjacent peaks \(i\) and \(i+1\) are connected by a line segment.

At night, John must carry at least one working lantern to move between peaks. There are k lanterns available for purchase. The j-th lantern is sold at peak \(p_j\) for cost \(c_j\) and works only at altitudes in the range \([a_j, b_j]\). (That is, if John’s current altitude is strictly below \(a_j\) or strictly above \(b_j\), then the lantern does not work. Note that lanterns are not damaged when they go out of their working range – they function again when John returns to a valid altitude.)

John starts a rescue mission by standing at peak \(p_j\) and buying the j-th lantern – it is guaranteed that \(a_j\le h_{p_j}\le b_j\). Afterwards, he may perform any of the following operations any number of times:

• Buy a lantern at his current peak (if available there). Once bought, a lantern is permanently available.
• If his current peak is \(p\) (with \(p > 1\)), he may move to peak \(p-1\).
• If his current peak is \(p\) (with \(p < n\)), he may move to peak \(p+1\).

However, John is only allowed to move between peaks if at every moment he has at least one lantern that is working at his current altitude. In other words, if at any time his altitude is \(x\), then at least one lantern sold (and purchased) must satisfy \(a\le x\le b\) for its interval \([a,b]\).

Observe that if John buys a set of lanterns with working intervals \(I_1, I_2, \dots, I_m\) (including the initial lantern) and the union of these intervals covers \([1,n]\) (i.e. \(\bigcup_{i=1}^m I_i = [1,n]\)), then every mountain peak \(i\) (since \(h_i\in\{1,2,\dots,n\}\)) is illuminated and reachable – moreover, one can always choose an order of purchases so that every new lantern is bought on a peak whose altitude lies in the current connected covered interval. (For instance, if John is at a mountain of altitude \(x\) and the set of purchased lanterns covers an interval \([L,R]\) with \(L\le x\le R\), then he may travel to any other peak \(y\) with \(y\in [L,R]\) because \(y\in [1,n]\subset [L,R]\) when the union is \([1,n]\).

Your task is: for each lantern \(j\) (with \(1\le j\le k\) and satisfying \(a_j\le h_{p_j}\le b_j\)), assume that John starts at peak \(p_j\) and immediately buys lantern \(j\). Determine the minimum total cost (including the cost \(c_j\) of the initial lantern) required so that by possibly buying additional lanterns, the union of the working intervals of all purchased lanterns becomes \([1,n]\) (i.e. the entire range of altitudes is covered). If it is impossible to achieve full coverage, output \(-1\).

Input Format: The first line contains two integers \(n\) and \(k\). The second line contains \(n\) integers \(h_1, h_2, \dots, h_n\) representing the altitudes of the peaks (a permutation of \(1,2,\dots,n\)). The next \(k\) lines each contain four integers \(p_j, c_j, a_j, b_j\) describing a lantern: it is sold at peak \(p_j\) at cost \(c_j\) and works in the altitude interval \([a_j,b_j]\). It is guaranteed that \(a_j\le h_{p_j}\le b_j\) for all \(j\).

Output Format: Output \(k\) lines, each containing one integer: the answer for the corresponding lantern query (the minimum total cost to achieve full coverage or \(-1\) if impossible).

Note on Correctness: A purchased set of lanterns is feasible if there exists an ordering of purchases such that every time a lantern is bought, its working interval intersects with the current union of working intervals; in that case, John can always travel on the connected chain of peaks because the union covers \([1,n]\). This condition is equivalent to requiring the union of the intervals to be exactly \([1,n]\).

Example: Suppose \(n=5\) and the mountain altitudes are given by \(h=[5,1,4,2,3]\). There are three lanterns:

• Lamp 1: sold at peak 1 with \(c=10\) and works in \([5,5]\).
• Lamp 2: sold at peak 3 with \(c=3\) and works in \([1,4]\).
• Lamp 3: sold at peak 5 with \(c=7\) and works in \([2,3]\).

Then, starting with any one of these lanterns it may be impossible to cover \([1,5]\); in such cases, the answer is \(-1\).

inputFormat

The input begins with a line containing two integers \(n\) and \(k\).
The second line contains \(n\) integers: \(h_1, h_2, \dots, h_n\) (a permutation of \(1,2,\dots,n\)).
Then follow \(k\) lines, each containing four integers: \(p_j\), \(c_j\), \(a_j\), and \(b_j\). It is guaranteed that \(a_j \le h_{p_j} \le b_j\) for each \(j\).

outputFormat

Output \(k\) lines. The \(j\)-th line contains a single integer: the minimum total cost needed (including the cost of the initial lantern) to achieve full coverage of altitudes \([1,n]\), or \(-1\) if it is impossible.

sample

5 3
5 1 4 2 3
1 10 5 5
3 3 1 4
5 7 2 3

-1
-1
-1

</p>