В столице Берляндии построили первую линию метро. Линия содержит $n + 1$ станцию и $n$ перегонов между ними, $i$-й перегон соединяет станции с номерами $i$ и $i + 1$ и стоимость проезда по нему равна $c_i$.

Перед полным открытием метро правительство Берляднии планирует сделать $m$ тестовых запусков метро. В $i$-м запуске будут открыты станции, номера которых не меньше $l_i$ и не больше $r_i$, а также все перегоны между этими станциями. В каждом тестовом запуске метро для каждой пары станций с номерами $a$ и $b$, таких что $a < b$, будет пущен поезд из станции $a$ в станцию $b$, с остановками на всех промежуточных станциях. Например если всего в метро 5 станций и во время тестового запуска будет открыты станции между 2 и 4, то будет пущен поезд со станции 2 на станцию 3, со станции 3 на станцию 4 и со станции 2 на станцию 4 с промежуточной остановкой на станции 3. Чтобы показать доступность метро, правительство Берляндии для каждого тестового запуска выбирает число $k_i$ и считает $k_i$-й минимальный по стоимости проезда перегон среди открытых перегонов в $i$-й день, при этом каждый перегон учитывается столько раз, сколько поездов по нему проезжает. Другими словами, правительство Берляднии хочет выписать стоимость проезда по каждому перегону столько раз, сколько поездов по нему проехало, после чего отсортировать полученныймассив по возрастанию и найти в нём $k_i$-е число. Помогите правительству Берляндии найти такой перегон для каждого из тестовых запусков.

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

В первой строке вводятся два целых числа $n$ и $m$ ($1 ⩽ n, m ⩽ 300 000$) — число перегонов и число тестовых запусков метро.

В следующей строке вводятся $n$ чисел $c_1, c_2, c_3, . . . , c_n (1 ⩽ c_i ⩽ 500 000)$ — стоимости проезда по перегонам метро.

Следующие $m$ строк описывают тестовые запуски. В $i$-й строке вводятся три целых числа $l_i, r_i$ и $k_i$ ($1 ⩽ li < r_i ⩽ n + 1, 1 ⩽ k_i ⩽ \frac{1}{6} (r_i − l_i)(r_i − l_i + 1)(r_i − l_i + 2)$) — первая открытая станция, последняя открытая станция и какой по стоимости перегон надо найти.

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

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

Система оценки

Каждый тест в каждой группе оценивается в 5 баллов.

Подзадачи