Kth Character
Given a string $$S$$ of length $$N$$, you have to answer $$Q$$ queries. Each query includes a range ($$L$$ and $$R$$) and a number $$K$$. For every query to have to print the lexicographically $$K$$th smallest alphabet in the given range.
INPUT
- The first line includes two integers $$N$$ and $$Q$$. $$N$$ representing the length of the string and $$Q$$ representing the number of queries.
- Second line contains the string $$S$$.
- Next $$Q$$ lines contain 3 integers $$L$$, $$R$$ and $$K$$
OUTPUT
The output should contain q lines, each line representing the $$K$$th character in the given range of the query.
CONSTRAINT
- 1 <= $$N$$ <= 1000000
- 1 <= $$Q$$ <= 1000000
- 1 <= $$L$$ <= $$R$$ <= 1000000
- 1 <= $$K$$ <= $$R$$ - $$L$$ + 1
- The string consists of small english alphabets
Time Limit:
5.0 sec(s)
for each input file.
Memory Limit:
256 MB
Source Limit:
1024 KB