K-те число
Ви працюєте на компанію МакроХард у відділі структури даних. Після невдалого розв'язання попередньої задачі про вставки ключів, Вас попросили написати нову структуру даних, яка дозволяє швидко знаходити k-ту порядкову статистику на заданому відрізку.
Задано масив a[1...n] різних цілих чисел. Необхідно відповідати на питання Q(i, j, k) наступного виду: "Знайти k-те число на відрізку a[i...j], якщо усі числа на цьому відрізку попередньо відсортувати".
Наприклад, розглянемо відрізок a = (1, 5, 2, 6, 3, 7, 4). Розглянемо запит Q(2, 5, 3). Відрізком a[2...5] буде (5, 2, 6, 3). Відсортувавши числа, отримаємо (2, 3, 5, 6). Третім елементом буде 5. Відповіддю на запит буде 5.
Вхідні дані
Перший рядок містить розмір масиву n та кількість запитів m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000).
Другий рядок містить n різних цілих чисел, які не перевищують 10^9 за абсолютним значенням - масив чисел, до якого будуть задаватись запити.
Наступні m рядків містять запити, кожен з яких складається з трьох чисел: i, j та k (0 ≤ i ≤ j ≤ n, 0 ≤ k ≤ j - i + 1) і являє собою запит Q(i, j, k).
Вихідні дані
Для кожного запиту вивести k-те число у відсортованому відрізку a[i...j].