Given a string(S) of alphabets(lower case only,a-z) of length N<(10**6), do two kind of operations(total of M<(10**5):
Type 1: 0 index c: Replace S[index] by char c.
Type 2: 1 LeftLimit RightLimit K : Print the lexicographically Kth smallest character in the sub-string of String S starting from LeftLimit to RightLimit, inclusively.(The lexicographic order means that the words are arranged in a similar fashion as they are presumed to appear in a dictionary)
Input format:
The first line contains 2 space separated integers N and Q, denoting the length of the string and the number of operations respectively.
The next line has a string S of length N.
The next Q lines denote the update/print operations, where 0 and 1 denote the type of operation which has to happen.
Output format:
For each print operation, output the lexicographically Kth smallest character in the substring of S starting from LeftLimit to RightLimit if possible, else print "Out of range." (Without quotes)
1 <= Size of the string(N) <= 10**6
1 <= Number of queries(M) <= 10**5
1 <= LeftLimit, RightLimit, index <= N
c is a lowercase Latin letter only
1 <= K <= N
S contains only lowercase latin letters (a to z).
Sample Input
5 3
aabbc
1 2 5 3
0 3 a
1 3 3 1
Sample Output
b
a
Which datastructure should be used?I think BIT or segment tree should be used,but how ? How to do the lexicographically kth one?( i saw this problem while doing xseed hiring challenge at hackerearth)