Descripción

En su visita a Cuba, el granjero John ha llevado su rebaño de vacas a una excursión en la Sierra Maestra. Luego de un rato, el cielo se oscureció y la excursión terminó. Sin embargo, algunas vacas han quedado atrapadas a lo largo de la cordillera y ahora John tiene que ir a rescatarlas.

La cordillera que las vacas están cruzando se puede representar con una serie de ~N~ vértices en un plano 2D vertical. Vamos a llamar a estos vértices "picos". Los picos están numerados del ~1~ al ~N~, en orden. Gracias a la colaboración de su guía Eduardo, el granjero John logró saber las cordenadas de cada pico, más precisamente, el granjero John sabe que la cordenada del pico ~i~ es ~(i, H_i)~, donde ~H_i~ indica la altitud del pico ~i~. Se garantiza que ~H_1, H_2, \ldots, H_N~ es una permutación de ~1\ldots N~. Además, Eduardo le informó al granjero John que los picos ~i~ e ~i+1~ están conectados por un camino oscuro y lleno de fango.

Al ser de noche, John no puede moverse a ninguna parte de la montaña si no tiene una linterna que funcione. Por suerte, hay ~K~ linternas que puede comprar. Para cada ~j~ (~1 \le j \le K~), la linterna ~j~ se puede comprar en el pico ~P_j~ por ~C_j~ pesos cubanos.

Desafortunadamente, la linterna ~j~ solo funciona cuando la altitud de John está en el rango ~[A_j, B_j]~. En otras palabras, cuando la altitud de John sea estrictamente menor que ~A_j~ o estrictamente mayor que ~B_j~ la linterna ~j~ no funcionará. Note que las linternas no se rompen cuando John sale de su rango de funcionamiento. Por ejemplo, cuando la altitud de John excede a ~B_j~, la linterna ~j~ deja de funcionar, pero tan pronto como John regrese a la altitud ~B_j~ la linterna funcionará de nuevo.

Si John está el pico ~P~, él puede realizar una de las siguientes tres acciones:

• Él puede comprar una de las linternas disponibles en el pico ~P~. Una vez que compra una linterna, puede usarla siempre que la necesite.
• Si ~P > 1~, él puede caminar al pico ~P-1~.
• Si ~P < N~, él puede caminar al pico ~P+1~.

John nunca debe moverse sin una linterna que funcione. Él solo puede caminar entre dos picos adyacentes si, en cada momento del trayecto, al menos una de las linternas que posee funciona (no es necesario que la linterna que funcione sea la misma durante todo el trayecto).

Por ejemplo, supongamos que el granjero John se encuentra actualmente en un pico con altitud ~4~ y desea ir a un pico adyacente con altitud ~1~. Si John tiene linternas que funcionan en los rangos de altitud ~[1, 3]~ y ~[3,4]~ esto le permitirá caminar de un pico al otro. Sin embargo, si John tiene linternas que solo funcionan en los rangos ~[1, 1]~ y ~[2, 5]~ entonces John no podrá caminar entre esos dos picos ya que ninguna de sus linternas funcionarán en la altitud ~1.314~

Tarea

Tu tarea consiste en encontrar la respuesta a una serie de preguntas independientes.

Para cada linterna ~j~ (~1 \le j \le N~) que cumpla que ~A_j \le H_{P_j} \le B_j~, supongamos que John empieza su búsqueda en el pico ~P_j~ comprando la linterna ~j~. Para poder buscar en toda la cordillera, tiene que visitar cada uno de los ~N~ picos al menos una vez realizando repetidamente una de las tres acciones descritas anteriormente. Para cada ~j~ determina el mínimo número de pesos cubanos que John tiene que gastar para poder buscar en toda la cordillera (esto incluye la compra inicial de la linterna ~j~).

Entrada

La primera línea de la entrada contiene dos enteros ~N~ y ~K~ (~1 \le N, K \le 2000~), el número de picos y el número de linternas disponibles, respectivamente.

La segunda línea contiene ~N~ enteros separados por espacio ~H_1, H_2, \ldots, H_N~ (~1 \le H_i \le N~), la altura de cada pico. Se asegura que los valores de ~H_i~ forman una permutación de ~1~ a ~N~.

La ~j-~ésima de las siguientes ~K~ líneas contiene cuatro enteros separados por un espacio ~P_j, C_j, A_j, B_j~ (~1 \le P_j \le N~, ~1 \le C_j \le 10^6~, ~1 \le A_j \le B_j \le N~), el pico donde está la linterna ~j~, su costo y el rango de alturas en el que funciona, respectivamente.

Salida

Para cada ~j~ (~1 \le j \le K~):

• Si ~H_{P_j}~ está fuera del rango ~[A_j, B_j]~, imprime ~-1~.
• Si John no puede buscar en toda la cordillera empezando con la linterna ~j~, imprime ~-1~.
• Si puede buscar en toda la cordillera y ~H_{P_j}~ está en el rango ~[A_j, B_j]~, imprime el mínimo número de pesos cubanos que tiene que gastar para conseguirlo si empieza comprando la linterna ~j~.

Subtareas

• Subtarea 1: ~N \le 20~, ~K \le 6~ (~9~ puntos)
• Subtarea 2: ~N \le 70~, ~K \le 70~ (~12~ puntos)
• Subtarea 3: ~N \le 300~, ~K \le 300~ y ~H_i = i~ para todo ~1 \le i \le N~ (~23~ puntos)
• Subtarea 4: ~N \le 300~, ~K \le 300~ (~16~ puntos)
• Subtarea 5: Sin restricciones adicionales (~40~ puntos)

Ejemplos

Entrada 1

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

Salida 1

7
-1
4
10
30
-1
-1
-1

Si John empieza comprando la linterna ~1~ en el pico ~3~ puede hacer lo siguiente:

• caminar dos veces hacia la izquierda hasta el pico ~1~
• comprar la linterna ~2~
• caminar hacia la derecha hasta el pico ~4~
• comprar la linterna ~3~
• caminar hacia la derecha hasta el pico ~7~

En este punto, John ha visitado cada uno de los picos al menos una vez y ha gastado un total de ~1 + 2 + 4 = 7~ pesos cubanos.

John no puede empezar comprando las linternas ~2, 6~ o ~7~ porque no funcionan a la altura en las que las puede comprar. Por lo tanto la respuesta es ~-1~.

Si John empieza comprando las linternas ~3~ o ~4~, puede visitar todos los picos sin comprar ninguna linterna extra.