All Tracks Data Structures Hash Tables Basics of Hash Tables Problem

Kth Character
/
No tags
Problem
Editorial
Analytics

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
SAMPLE INPUT
10 5
ababcdabcd
1 4 2
1 4 3
1 5 5
1 10 8
7 10 3
SAMPLE OUTPUT
a
b
c
c
c
Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?