\begin{problem}{Иллюзия размена}{стандартный ввод}{стандартный вывод}{2.5 секунд}{512 мегабайт}

Четверо Всадников готовят новый трюк. На сцене перед зрителями стоит \textit{магическая доска}, на которой изначально записано одно число~$S$ --- сумма денег, которая якобы лежит в банковской ячейке.

За один ход маги могут выполнить следующий <<номер>>:
\begin{itemize}
    \item выбрать какое-то число $y$, записанное на доске;
    \item стереть $y$;
    \item вместо него записать два натуральных числа $a$ и $b$ такие, что $y = a + b$.
\end{itemize}

Однако за каждый такой размен продюсеру приходится платить за спецэффекты $a \cdot b$ монет.

В какой-то момент Всадники хотят, чтобы на доске оказались заранее заданные числа~--- это суммы, которые зрители якобы увидят на своих счетах после трюка. При этом на доске могут остаться и какие-то лишние числа; главное, чтобы все нужные суммы уже присутствовали.

Дан массив из $n$ чисел $x_1, x_2, \dots, x_n$~--- потенциальные финальные суммы для разных вариантов трюка.

Продюсер задаёт $q$ вопросов. Каждый вопрос описывает одну постановку:
\begin{itemize}
    \item выбирается подотрезок массива $x$~--- от $l$ до $r$;
    \item задаётся исходная сумма на доске $S$.
\end{itemize}

Для каждого такого запроса нужно определит можно ли, начиная с единственного числа $S$ на доске, с помощью описанных действий получить набор чисел $x_l, x_{l+1}, \dots, x_r$ (порядок не важен, на доске могут быть дополнительно другие числа). Если можно~--- сообщить, какова минимальная суммарная стоимость всех разменов в монетах, необходимая для реализации такого трюка; иначе~--- сообщить, что трюк невозможен.



\InputFile
В первой строке заданы два числа $n$ и $q$~--- количество чисел в массиве и количество запросов ($1 \le n, q \le 2 \cdot 10^5$).

Во второй строке заданы $n$ чисел $x_1, x_2, \dots, x_n$~--- элементы массива ($1 \le x_i \le 10^6$).

Каждая из следующих $q$ строк содержит запрос в формате $l$, $r$, $S$ ($1 \leq l \leq r \leq n$; $1 \leq S \leq 10^9$).


\OutputFile
Для каждого запроса выведите в отдельной строке минимальное количество монет, которое должен потратить продюсер, чтобы реализовать такой трюк~--- или $-1$, если получить требуемый набор чисел невозможно.



\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\end{problem}

