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, \ldots, 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$.