Фермер Джон взяв своє стадо корів на пішохідну екскурсію в Альпи! Через деякий час небо потемніло і екскурсія закінчилась. Однак деякі корови залишились в пастці по всьому гірському хребту і Джон збирається врятувати усіх їх! Гірський хребет, який корови зараз проходять, може бути представлений як серія з $n$ точок в 2D площині. Ми будемо називати ці точки <<вершинами>>. Вершини пронумеровані від 1 до $n$, в такому ж порядку. Вершина $i$ має координати $(i, h_i)$. Значення $h_i$ позначає \textbf{висоту} вершини $i$. Гарантується, що $h_1,h_2,\ldots,h_n$ формують перестановку $1 \ldots 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$, він може здійснити одну з трьох наступних операцій: \begin{itemize} \item Він може купити один з ліхтарів, що доступні на вершині $p$. Як тільки він купує ліхтар, він може використовувати його завжди. \item Якщо $p > 1$, він може перейти до вершини $p-1$. \item Якщо $p < n$, він може перейти до вершини $p+1$. \end{itemize} Джон ніколи не повинен рухатись без справного ліхтаря. Він може переходити між двома вершинами тільки якщо в кожен момент його дороги існує хоча б один ліхтар, який він придбав і який працює. (Це не обов'язково має бути один і той же ліхтар на всю дорогу). Наприклад, уявімо, що Фермер Джон зараз знаходиться на вершині з висотою $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$.) \InputFile Перший рядок містить $n$ та $k$ ($1 \leq n \leq 2000$, $1 \leq k \leq 2000$)~--- кількість вершин гірського хребта та кількість доступних ліхтарів відповідно. Другий рядок містить $n$ відокремлених пробілом цілих чисел $h_1,h_2,\ldots,h_n$ ($1 \leq h_i \leq n$): висоти кожної з вершин. Гарантується, що значення $h_i$ формують перестановку чисел від $1$ до $n$. $j$-ий рядок з наступних $k$ рядків містить чотири числа, відокремлених пробілом, $p_j$, $c_j$, $a_j$, та $b_j$ ($1 \leq p_j \leq n$, $1 \leq c_j \leq 10^6$, $1 \leq a_j \leq b_j \leq n$)~--- номер вершини, де ліхтар $j$ може бути придбаний, його ціна та діапазон відповідно. \OutputFile Для кожного $j$ ($1 \le j \le k$) виведіть один рядок: \begin{itemize} \item Якщо $h_{p_j}$ виходить за межі діапазону $[a_j,b_j]$, виведіть $-1$. \item Інакше, якщо Джон не може пройти усі вершини гірського хребта спершу купуючи ліхтар $j$, виведіть $-1$. \item Інакше, виведіть мінімальну кількість франків, що Джон має витратити аби відвідати кожну вершину гірського хребта, якщо він починає купуючи ліхтар $j$. \end{itemize} \Note Якщо Джон починає з покупки ліхтаря $1$ на вершині $3$, він може здійснити таку послідовність операцій: \begin{itemize} \item йде ліворуч двічі до вершини $1$ \item купує ліхтар $2$ \item йде праворуч до вершини $4$ \item купує ліхтар $3$ \item йде праворуч до вершини $7$ \end{itemize} В такому випадку, Джон відвідає кожну вершину щонайменше один раз і витратить в сумі $1+2+4=7$ франків. Джон не може почати купуючи ліхтарі $2$, $6$, або $7$, оскільки вони не працюють на висоті, де вони можуть бути придбані. Тому, відповідь для цих ліхтарів $-1$. Якщо Джон починає з купівлі ліхтаря $3$ або $4$, він може відвідати усі вершини без купівлі додаткових ліхтарів. Якщо Джон починає з купівлі ліхтаря $5$, він має також купити ліхтар $4$ пізніше. Якщо Джон починає з купівлі ліхтаря $8$, він застрягне на вершині $7$. Навіть якщо він купить ліхтар $7$, він все одно не зможе перейти від вершини $7$ до вершини $6$. \Scoring Блок 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$ балів): без додаткових обмежень.