Ліхтарі

Фермер Джон взяв своє стадо корів на пішохідну екскурсію в Альпи! Через деякий час небо потемніло і екскурсія закінчилась. Однак деякі корови залишились в пастці по всьому гірському хребту і Джон збирається врятувати усіх їх!

Гірський хребет, який корови зараз проходять, може бути представлений як серія з $n$ точок в 2D площині. Ми будемо називати ці точки «вершинами». Вершини пронумеровані від 1 до $n$, в такому ж порядку. Вершина $i$ має координати $(i,h_i)$. Значення $h_i$ позначає висоту вершини $i$. Гарантується, що $h_1,h_2,\dots ,h_n$ формують перестановку $1\dots n$. (Це означає, що для кожного $j=1,...,n$, ми маємо $h_i=j$ рівно для одного $i\in \{1,...,n\}$.)

Для кожного $i$ ($1\le i<n$), вершини $i$ та $i+1$ з'єднані одним прямим відрізком.

Оскільки вже ніч, Джон не може подорожувати до будь-якої частини гори, якщо не має з собою як мінімум одного ліхтаря, що функціонує. На щастя, є $k$ ліхтарів, що доступні для покупки. Для кожного $j$ ($1\le j\le k$), $j$-ий ліхтар можна купити на вершині $p_j$ за $c_j$ франків.

На жаль, $j$-ий ліхтар може працювати тільки коли Джон знаходиться на висоті в межі $[a_j,b_j]$. Іншими словами, коли поточна висота строго менша за $a_j$ або строго більша за $b_j$, ліхтар $j$ не працює. Зверніть увагу, що ліхтарі не ламаються, коли залишають свій діапазон висот. Наприклад, коли висота Джона перевищує $b_j$, ліхтар $j$ перестає працювати, але як тільки Джон повернеться на висоту $b_j$ ліхтар почне працювати знову.

Якщо Джон зараз знаходиться на вершині $p$, він може здійснити одну з трьох наступних операцій:

• Він може купити один з ліхтарів, що доступні на вершині $p$. Як тільки він купує ліхтар, він може використовувати його завжди.

• Якщо $p>1$, він може перейти до вершини $p-1$.

• Якщо $p<n$, він може перейти до вершини $p+1$.

Джон ніколи не повинен рухатись без справного ліхтаря. Він може переходити між двома вершинами тільки якщо в кожен момент його дороги існує хоча б один ліхтар, який він придбав і який працює. (Це не обов'язково має бути один і той же ліхтар на всю дорогу).

Наприклад, уявімо, що Фермер Джон зараз знаходиться на вершині з висотою $4$ і бажає перейти до сусідньої вершини з висотою $1$. Якщо Джон має ліхтарі, які працюють на діапазонах висот $[1,3]$ та $[3,4]$, то він зможе перейти від однієї вершини до іншої.

Однак, якщо Джон має ліхтарі, які працюють на діапазонах висот $[1,1]$ та $[2,5]$, тоді Джон не може перейти між цими двома вершинами: оскільки жоден з ліхтарів не буде працювати на висоті $1.47$.

Ваша задача визначити відповідь для різних незалежних один від одного запитів.

Для кожного $1\le j\le k$ таких, що $a_j\le h_{p_j}\le b_j$, уявімо, що Джон починає свою подорож з вершини $p_j$ купуючи ліхтар $j$. Аби пройти повністю гірський хребет, він має відвідати кожну з усіх $n$ вершин хоча б один раз послідовно виконуючи одну з трьох операцій описаних вище. Для кожного з $j$, визначіть мінімальну кількість франків, що потрібно заплатити Джону для того, щоб обійти увесь гірський хребет. (Ця вартість включає в себе початкову вартість покупки ліхтаря $j$.)

Вхідні дані

Перший рядок містить $n$ та $k$ ($1\le n\le 2000$, $1\le k\le 2000$) — кількість вершин гірського хребта та кількість доступних ліхтарів відповідно.

Другий рядок містить $n$ відокремлених пробілом цілих чисел $h_1,h_2,\dots ,h_n$ ($1\le h_i\le n$): висоти кожної з вершин. Гарантується, що значення $h_i$ формують перестановку чисел від $1$ до $n$.

$j$-ий рядок з наступних $k$ рядків містить чотири числа, відокремлених пробілом, $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$) — номер вершини, де ліхтар $j$ може бути придбаний, його ціна та діапазон відповідно.

Вихідні дані

Для кожного $j$ ($1\le j\le k$) виведіть один рядок:

• Якщо $h_{p_j}$ виходить за межі діапазону $[a_j,b_j]$, виведіть $-1$.

• Інакше, якщо Джон не може пройти усі вершини гірського хребта спершу купуючи ліхтар $j$, виведіть $-1$.

• Інакше, виведіть мінімальну кількість франків, що Джон має витратити аби відвідати кожну вершину гірського хребта, якщо він починає купуючи ліхтар $j$.

Приклади

Примітка

Якщо Джон починає з покупки ліхтаря $1$ на вершині $3$, він може здійснити таку послідовність операцій:

• йде ліворуч двічі до вершини $1$

• купує ліхтар $2$

• йде праворуч до вершини $4$

• купує ліхтар $3$

• йде праворуч до вершини $7$

В такому випадку, Джон відвідає кожну вершину щонайменше один раз і витратить в сумі $1+2+4=7$ франків.

Джон не може почати купуючи ліхтарі $2$, $6$, або $7$, оскільки вони не працюють на висоті, де вони можуть бути придбані. Тому, відповідь для цих ліхтарів $-1$.

Якщо Джон починає з купівлі ліхтаря $3$ або $4$, він може відвідати усі вершини без купівлі додаткових ліхтарів.

Якщо Джон починає з купівлі ліхтаря $5$, він має також купити ліхтар $4$ пізніше.

Якщо Джон починає з купівлі ліхтаря $8$, він застрягне на вершині $7$. Навіть якщо він купить ліхтар $7$, він все одно не зможе перейти від вершини $7$ до вершини $6$.

Оцінювання

Блок 1 ($9$ балів): $n\le 20$ та $k\le 6$.

Блок 2 ($12$ балів): $n\le 70$ та $k\le 70$.

Блок 3 ($23$ бали): $n\le 300$, $k\le 300$ та $h_i=i$ для усіх $1\le i\le n$.

Блок 4 ($16$ балів): $n\le 300$, $k\le 300$.

Блок 5 ($40$ балів): без додаткових обмежень.