Problem Statement

You are given a string $S$ consisting of $N$ lowercase English letters.

Process $Q$ queries.

The $i$-th query is as follows.
Among the strings obtained by arbitrarily rearranging the substring of $S$ from the $L_i$-th character to the $R_i$-th character, take the lexicographically smallest one and print its $X_i$-th character.

Input

$N\ \ Q$
$S$
$L_1\ \ R_1\ \ X_1$
$L_2\ \ R_2\ \ X_2$
$\ \vdots$
$L_Q\ \ R_Q\ \ X_Q$

• $S$ is a string of length $N$ consisting only of lowercase English letters
• $ 1 \leq N,Q \leq 10^4$
• $ 1 \leq L_i \leq R_i \leq N(1\leq i \leq Q)$
• $ 1 \leq X_i \leq R_i-L_i+1(1\leq i \leq Q)$
• All inputs other than $S$ are integers

Output

Print $Q$ lines. On the $i$-th line, print the answer to the $i$-th query, followed by a newline.

Sample

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