K-те число

Ви працюєте в компанії Macrohard у відділі структур даних. Після невдалого виконання попереднього завдання про вставку ключів вам доручили розробити нову структуру даних, яка зможе ефективно відповідати на запити про $k$-ту порядкову статистику на відрізку масиву.

Задано масив a_1, a_2, \dots, a_n, що складається з $n$ різних цілих чисел. Вашій програмі потрібно відповісти на декілька запитів Q(i, j, k) такого типу: «Яке число буде $k$-тим за величиною на відрізку a_i, a_{i+1}, \dots, a_j, якщо цей відрізок відсортувати?»

Наприклад, розглянемо масив a = (1, 5, 2, 6, 3, 7, 4). Запит Q(2, 5, 3) вимагає розглянути відрізок a_2, a_3, a_4, a_5 = (5, 2, 6, 3). Відсортувавши цей відрізок, отримаємо (2, 3, 5, 6); третім числом буде $5$, отже, відповідь на цей запит — $5$.

\InputFileПерший рядок містить два цілі числа $n$ та $m$ (1 \le n \le 100\,000, 1 \le m \le 5\,000) — розмір масиву та кількість запитів.

Другий рядок містить $n$ різних цілих чисел a_1, a_2, \dots, a_n за модулем не більших за 10^9.

Кожен із наступних $m$ рядків містить три цілі числа $i$, $j$, і $k$ (1 \le i \le j \le n, 1 \le k \le j-i+1), що описують запит Q(i, j, k).

\OutputFileДля кожного запиту виведіть відповідь: $k$-те за величиною число у відсортованому відрізку a_i, \dots, a_j.