Фонари

Фермер Джон отправился со своим стадом коров в поход по Альпам! Однако вскоре небо потемнело, и прогулка закончилась. Некоторые коровы оказались в ловушке на горном хребте, и Джон намерен их всех спасти!

Горный хребет, по которому идут коровы, можно представить как последовательность из $n$ точек на плоскости. Эти точки мы будем называть "вершинами". Вершины пронумерованы от 1 до $n$ в порядке их следования. Вершина $i$ имеет координаты $(i,h_i)$, где $h_i$ обозначает высоту вершины $i$. Гарантируется, что $h_1,h_2,\dots ,h_n$ образуют перестановку чисел от 1 до $n$. Это значит, что для каждого $j=1,\dots ,n$, существует ровно одно $i\in \{1,\dots ,n\}$, для которого $h_i=j$.

Каждая пара соседних вершин $i$ и $i+1$ ($1\le i<n$) соединена прямым отрезком.

Поскольку уже ночь, Джон не может перемещаться по горному хребту без работающего фонаря. К счастью, у него есть возможность приобрести $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$ баллов): без дополнительных ограничений.