Иллюзия размена
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

За один ход маги могут выполнить следующий «номер»:

- выбрать какое-то число $$$y$$$, записанное на доске;
- стереть $$$y$$$;
- вместо него записать два натуральных числа $$$a$$$ и $$$b$$$ такие, что $$$y = a + b$$$.

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

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

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

Продюсер задаёт $$$q$$$ вопросов. Каждый вопрос описывает одну постановку:

- выбирается подотрезок массива $$$x$$$ — от $$$l$$$ до $$$r$$$;
- задаётся исходная сумма на доске $$$S$$$.

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

Входные данные

В первой строке заданы два числа $$$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$$$).

Выходные данные

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

Пример

Входные данные

    5 61 2 3 4 52 4 101 3 63 5 101 5 202 2 52 2 2

Выходные данные

    35
    11
    -1
    160
    6
    0