Фермер Джон взяв своє стадо корів на пішохідну екскурсію в Альпи! Через деякий час небо потемніло і екскурсія закінчилась. Однак деякі корови залишились в пастці по всьому гірському хребту і Джон збирається врятувати усіх їх!
Гірський хребет, який корови зараз проходять, може бути представлений як серія з n точок в 2D площині. Ми будемо називати ці точки «вершинами». Вершини пронумеровані від 1 до n, в такому ж порядку. Вершина i має координати (i,hi). Значення hi позначає висоту вершини i. Гарантується, що h1,h2,…,hn формують перестановку 1…n. (Це означає, що для кожного j=1,...,n, ми маємо hi=j рівно для одного i∈{1,...,n}.)
Для кожного i (1≤i<n), вершини i та i+1 з'єднані одним прямим відрізком.
Оскільки вже ніч, Джон не може подорожувати до будь-якої частини гори, якщо не має з собою як мінімум одного ліхтаря, що функціонує. На щастя, є k ліхтарів, що доступні для покупки. Для кожного j (1≤j≤k), j-ий ліхтар можна купити на вершині pj за cj франків.
На жаль, j-ий ліхтар може працювати тільки коли Джон знаходиться на висоті в межі [aj,bj]. Іншими словами, коли поточна висота строго менша за aj або строго більша за bj, ліхтар j не працює. Зверніть увагу, що ліхтарі не ламаються, коли залишають свій діапазон висот. Наприклад, коли висота Джона перевищує bj, ліхтар j перестає працювати, але як тільки Джон повернеться на висоту bj ліхтар почне працювати знову.
Якщо Джон зараз знаходиться на вершині p, він може здійснити одну з трьох наступних операцій:
Він може купити один з ліхтарів, що доступні на вершині p. Як тільки він купує ліхтар, він може використовувати його завжди.
Якщо p>1, він може перейти до вершини p−1.
Якщо p<n, він може перейти до вершини p+1.
Джон ніколи не повинен рухатись без справного ліхтаря. Він може переходити між двома вершинами тільки якщо в кожен момент його дороги існує хоча б один ліхтар, який він придбав і який працює. (Це не обов'язково має бути один і той же ліхтар на всю дорогу).
Наприклад, уявімо, що Фермер Джон зараз знаходиться на вершині з висотою 4 і бажає перейти до сусідньої вершини з висотою 1. Якщо Джон має ліхтарі, які працюють на діапазонах висот [1,3] та [3,4], то він зможе перейти від однієї вершини до іншої.
Однак, якщо Джон має ліхтарі, які працюють на діапазонах висот [1,1] та [2,5], тоді Джон не може перейти між цими двома вершинами: оскільки жоден з ліхтарів не буде працювати на висоті 1.47.
Ваша задача визначити відповідь для різних незалежних один від одного запитів.
Для кожного 1≤j≤k таких, що aj≤hpj≤bj, уявімо, що Джон починає свою подорож з вершини pj купуючи ліхтар j. Аби пройти повністю гірський хребет, він має відвідати кожну з усіх n вершин хоча б один раз послідовно виконуючи одну з трьох операцій описаних вище. Для кожного з j, визначіть мінімальну кількість франків, що потрібно заплатити Джону для того, щоб обійти увесь гірський хребет. (Ця вартість включає в себе початкову вартість покупки ліхтаря j.)
Перший рядок містить n та k (1≤n≤2000, 1≤k≤2000) — кількість вершин гірського хребта та кількість доступних ліхтарів відповідно.
Другий рядок містить n відокремлених пробілом цілих чисел h1,h2,…,hn (1≤hi≤n): висоти кожної з вершин. Гарантується, що значення hi формують перестановку чисел від 1 до n.
j-ий рядок з наступних k рядків містить чотири числа, відокремлених пробілом, pj, cj, aj, та bj (1≤pj≤n, 1≤cj≤106, 1≤aj≤bj≤n) — номер вершини, де ліхтар j може бути придбаний, його ціна та діапазон відповідно.
Для кожного j (1≤j≤k) виведіть один рядок:
Якщо hpj виходить за межі діапазону [aj,bj], виведіть −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≤20 та k≤6.
Блок 2 (12 балів): n≤70 та k≤70.
Блок 3 (23 бали): n≤300, k≤300 та hi=i для усіх 1≤i≤n.
Блок 4 (16 балів): n≤300, k≤300.
Блок 5 (40 балів): без додаткових обмежень.