Phần tử nhỏ thứ k trên đoạn

Cho mảng $a_1,a_2,\dots ,a_n$ và $q$ truy vấn. Mỗi truy vấn gồm ba số $l,r,k$ ($1\le l\le r\le n$, $1\le k\le r-l+1$): hãy in ra phần tử nhỏ thứ $k$ trong đoạn $a_l,a_{l+1},\dots ,a_r$ (nếu đoạn có nhiều phần tử bằng nhau, mỗi vị trí tính riêng).

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $q$.
• Dòng thứ hai: $n$ số nguyên $a_1,\dots ,a_n$.
• $q$ dòng tiếp theo, mỗi dòng ba số $l,r,k$ mô tả một truy vấn.

Dữ liệu ra

In $q$ dòng — mỗi dòng là phần tử nhỏ thứ $k$ tương ứng của đoạn.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le a_i\le {10}^9$
• $1\le l\le r\le n$ và $1\le k\le r-l+1$

Ví dụ

Ghi chú

• "Nhỏ thứ $k$" hiểu theo nghĩa nếu sắp xếp đoạn không giảm thì phần tử ở vị trí $k$ chính là đáp án.
• Các vị trí lặp lại được tính riêng: nếu trong đoạn có hai số $1$ thì cả hai đều đóng góp vào thứ tự.