# 可怜的狗狗

## 题目描述

小卡家有  $n$ 只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。

可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第  $i$ 只到第  $j$ 只狗中第  $k$ 漂亮的狗狗喂食（好狠心的人啊）。而且为了保证某一只狗狗不会被喂太多次，他喂的每个区间  $[i,j]$ 不互相包含。

## 输入格式

第一行输入两个数  $n,m$， $m$ 表示嘉嘉喂食的次数

第二行  $n$ 个整数，表示第  $i$ 只狗的漂亮值为  $a_i$。

接下来  $m$ 行，每行  $3$ 个整数  $i,j,k$，表示询问这次喂食喂第  $i$ 到第  $j$ 只狗中第  $k$ 漂亮的狗的漂亮值。

## 输出格式

$m$ 行，每行一个整数，表示每一次喂的那只狗漂亮值为多少。

## 样例 #1

### 样例输入 #1

```
7 2
1 5 2 6 3 7 4
1 5 3
2 7 1
```

### 样例输出 #1

```
3
2
```

## 提示

$1\le n \le 3\times 10^5 ,1\le m \le5\times10^4,0\le a_i<2^{31}$，且 $a_i$ 互不相同。