K-те число (Easy)#1150
Ви працюєте у департаменті структур даних компанії Macrohard. Після вашої невдалої попередньої спроби вирішити задачу вставки ключів, вас попросили розробити нову структуру даних, яка зможе швидко знаходити k-ту порядкову статистику на заданому відрізку масиву.
Вам задано масив a[1 \ldots n] з різних цілих чисел. Необхідно відповісти на запити вигляду Q(i, j, k): "Знайти -те число у підмасиві a[i \ldots j], якщо всі його елементи відсортувати."
Наприклад, нехай a = (1, 5, 2, 6, 3, 7, 4). Для запиту Q(2, 5, 3) підмасив a[2 \ldots 5] = (5, 2, 6, 3). Відсортувавши цей відрізок, отримаємо (2, 3, 5, 6), тому третім числом буде ; отже, відповідь — .
У першому рядку задано розмір масиву та кількість запитів (1 \le n, m \le 100).
У другому рядку міститься різних цілих чисел, модуль кожного з яких не перевищує 10^9 — масив .
Кожен з наступних рядків містить по три числа: , , (1 \le i \le j \le n, 1 \le k \le j-i+1), що відповідають запиту Q(i, j, k).
Для кожного запиту виведіть -те число у відсортованому відрізку a[i \ldots j].
Приклад 1