K-ci ədəd (Asan)

Siz Macrohard şirkətinin məlumat strukturları şöbəsində işləyirsiniz. Açar əlavəetmə problemini uğursuz şəkildə həll etdikdən sonra, sizdən tez bir zamanda verilmiş massiv seqmentində k-cı dərəcəli statistik tapmağa imkan verən yeni bir məlumat strukturu hazırlamağınızı xahiş ediblər.

Sizə $n$ fərqli tam ədəddən ibarət a[1 \ldots n] massivi verilir. Sorğular aşağıdakı formada olacaq: Q(i, j, k): "Əgər a[i \ldots j] seqmentinin bütün elementləri sıralansa, onun $k$-cı ədədi hansıdır?"

Məsələn, a = (1, 5, 2, 6, 3, 7, 4) massivini nəzərdən keçirək. Q(2, 5, 3) sorğusu üçün a[2 \ldots 5] = (5, 2, 6, 3). Bu seqmenti sıralasaq (2, 3, 5, 6) alınır, üçüncü ədəd $5$-dir; beləliklə, cavab $5$-dir.

Giriş

Birinci sətirdə massiv ölçüsü $n$ və sorğuların sayı $m$ verilir (1 \le n, m \le 100).

İkinci sətirdə $n$ fərqli tam ədəd verilir; onların modulu 10^9-u aşmır -- massiv $a$.

Sonrakı $m$ sətirin hər birində üç tam ədəd, $i$, $j$, və $k$ verilir (1 \le i \le j \le n, 1 \le k \le j-i+1) -- bu, Q(i, j, k) sorğusudur.

Çıxış

Hər bir sorğu üçün, sıralanmış a[i \ldots j] seqmentində $k$-cı ədədi çap edin.