Marisa planted $n$ apple trees in a row. Each tree, denoted as the $i^{th}$ tree, can grow apples of size $A_i$. For her research purposes, Marisa conducts $q$ queries, each in the form of $(l, r, k)$. In each query, she needs to find the $k^{th}$ smallest apple size among the trees in the range $[l, r]$. Please help her answering these queries.
### Input
- The first line contains two integers $n,q$.
- The second line contains $n$ integer $A_i$.
- The next $q$ lines, each line contains three integers $l,r,k$, a query.
### Output
- Print an integer, which represents the answer for each query.
### Constraints
- $1 \le n,q \le 10^5$
- $1 \le A_i \le 10^9$.
- $1 \le l \le r \le n$.
- $1 \le k \le r - l + 1$.
### Example
Input:
```
5 3
3 7 2 1 8
1 3 1
1 5 3
2 4 3
```
Output:
```
2
3
7
```
