Lexicographically Smallest Substring Query

You are given a string s of length \(n\) consisting of lowercase English letters. You are also given \(q\) queries. Each query is represented by three integers \(l\), \(r\) and \(k\), and requires you to find the lexicographically smallest substring of length \(k\) within the substring \(s[l..r]\) (here the indices are 1-indexed).

Input Constraints:

• \(1 \leq n \leq 10^5\)
• \(1 \leq q \leq 10^5\)
• \(1 \leq l \leq r \leq n\)
• \(1 \leq k \leq (r-l+1)\)

Example:

Input:
10 3
ababacbaba
1 10 3
3 8 2
1 5 4
Output:
aba
ab
abab

</p>

inputFormat

The first line consists of two integers \(n\) and \(q\), representing the length of the string and the number of queries respectively.

The second line contains the string \(s\) of length \(n\).

Then follow \(q\) lines, each containing three integers \(l\), \(r\), and \(k\) which represent a query.

outputFormat

For each query, output the lexicographically smallest substring of length \(k\) from the substring \(s[l..r]\) on a new line.

## sample

10 3
ababacbaba
1 10 3
3 8 2
1 5 4

aba
ab
abab

</p>