% Автор: Сергей Копелиович
% Источник: Сборы в Харькове, февраль 2013

\begin{problem}{K минимумов на отрезке}
{firstk.in}{firstk.out}
{1 секунда}{256 мегабайт}{}

Дан массив $a$ из $n$ целых чисел и $q$ запросов вида
<<вывести $k$ первых чисел в отсортированной версии отрезка $[l \dots r]$ нашего массива>>.

Пример: $n = 7$, $a = [6, 1, 5, 2, 4, 3, 1]$, $l = 2$, $r = 4$, $k = 2$.
Отрезок $[l \dots r] = [1, 5, 2]$.
Его отсортированная версия = $[1, 2, 5]$.
Первые $2$ числа = $[1, 2]$.

\InputFile

На первой строке число $n$ ($1 \le n \le 100\,000$).

На второй строке массив $a$ ($n$ целых чисел от $1$ до $10^9$).

На третьей строке количество запросов $q$ ($1 \le q \le 100\,000$).

Следующие $q$ строк содержат тройки чисел $l_i$ $r_i$ $k_i$ 

$1 \le l_i \le r_i \le n$, $1 \le k_i \le \min(r_i - l_i + 1, 10)$

\OutputFile

Для каждого из $q$ запросов выведите ответ ($k_i$ чисел) на отдельной строке.
Числа внутри одного запроса нужно выводить в порядке возрастания.
Для лучшего понимания условия и формата данных смотрите пример.

\Scoring

В этой задаче есть две группы тестов:

$n, q \le 100\,000$, $l_i \le l_{i+1}$, $r_i \le r_{i+1}$.

$n, q \le 30\,000$, $l_i$ и $r_i$ произвольны.

\Example

\begin{example}
\exmp{
7
6 1 5 2 4 3 1
4
1 7 7
2 4 2
3 5 1
5 7 2
}{
1 1 2 3 4 5 6
1 2
2
1 3
}%
\end{example}

\end{problem}
