Ліхтарі

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

Гірський хребет, який корови зараз проходять, може бути представлений як серія з $n$ точок в 2D площині. Ми будемо називати ці точки «вершинами». Вершини пронумеровані від 1 до $n$, в такому ж порядку. Вершина $i$ має координати (i, h_i). Значення h_i позначає висоту вершини $i$. Гарантується, що h_1,h_2,\ldots,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$.)