問題文

$N$ 文字の英小文字からなる文字列 $S$ が与えられます。

$Q$ 個のクエリを処理してください。

$i$ 番目のクエリの内容は以下の通りです。
$S$ の $L_i$ 文字目から $R_i$ 文字目までから成る部分文字列を任意に並べ替えたものの中で辞書順最小である文字列の $X_i$ 文字目を出力してください。

入力

$NQ$
$S$
$L_1{R}_1{X}_1$
$L_2{R}_2{X}_2$
$⋮$
$L_Q{R}_Q{X}_Q$

• $S$ は英小文字のみからなる長さ $N$ の文字列
• $1\le N,Q\le {10}^4$
• $1\le L_i\le R_i\le N(1\le i\le Q)$
• $1\le X_i\le R_i-L_i+1(1\le i\le Q)$
• $S$ 以外の入力はすべて整数

出力

$Q$ 行出力してください。 $i$ 行目には $i$ 番目のクエリに対する答えを出力し、改行してください。

サンプル

5 3
query
2 4 2
1 5 3
3 3 1

r
r
e

10 4
japanjapan
1 10 5
3 7 1
4 9 2
2 2 1

j
a
a
a

16 6
amazingmightyyyy
1 5 4
2 16 1
8 9 1
2 2 1
1 16 2
4 10 4

m
a
i
m
a
i