akash-and-the-assignment-1-12

Akash has lots of assignments to submit in his college. In one of the assignment he is given a string S of length N consisting of lowercase letters (a - z) only. Akash has to answer Q queries and for every query, he is given L, R and K. For each query he has to find the lexicographically Kth smallest character in  substring of S starting from L to R, inclusively. Help Akash in solving his assignment.

Input

First line contains 2 integers N and Q, length of string and number of queries. Next line has a string S of length N. Next Q lines contains 3 integers L, R and K.

Output

For each query output the lexicographically Kth smallest character in substring of S starting from L to R if possible, else print "Out of range" (without qoutes).

Constraints

1 ≤ N ≤ 5*10^4

1 ≤ Q ≤ 10^5

1 ≤ L  ≤ R ≤ N

1 ≤ K ≤ N

Note:
S contains only lowercase latin letters (a to z).

SAMPLE INPUT
6 2
abcdef
2 6 3
4 6 1

SAMPLE OUTPUT
d
d

Explanation

In first query, substring will be bcdef. 3rd smallest character in the substring is d.
In second query, substring will be def. 1st smallest character in the substring is d.

Source: hackerearth | Difficulty: EASY
Tags: String algorithms


Solutions:
size, queries = list(map(int, input().split()))
string ,size = input(), size +1
string = '0' +string

#prefix Computation
prefix = [ [0]*26 for  i in range(size)]
for j in range(1,size):
	diff = ord(string[j]) - ord('a')
	for val in range(26):
		if val == diff:
			prefix[j][val] = prefix[j-1][val] + 1
		else:
			prefix[j][val] = prefix[j-1][val]
			

for i in range(queries):
	l, r , k = list(map(int, input().split()))
	
	chk ,nthsmall = 0, 0
	
	while chk<26:
		nthsmall += prefix[r][chk] - prefix[l-1][chk]
		if nthsmall >=k:
			break
		chk += 1
	res = chr(97 + chk)
	if chk == 26:
		print("Out of range")
	else:
		print(res)


A = ord("a")
n, q = list(map(int, input().split()))
s = input().strip()
h = [26 * [0] for _ in range(n+1)]
for i in range(n):
	d = ord(s[i]) - A
	for j in range(26):
		h[i+1][j] = h[i][j]
	h[i+1][d] = h[i][d] + 1
   
for _ in range(q):
	l, r, k = list(map(int, input().split()))
	if k >  r - l + 1:
		print("Out of range")
	else:
		hl = [h[r][i] - h[l-1][i] for i in range(26)]
		for i in range(26):
			k -= hl[i]
			if k <= 0:
				print(chr(i + A))
				break


A = ord("a")
n, q = list(map(int, input().split()))
s = input().strip()
h = [26 * [0] for _ in range(n+1)]
for i in range(n):
	d = ord(s[i]) - A
	for j in range(26):
		h[i+1][j] = h[i][j]
	h[i+1][d] = h[i][d] + 1
   
for _ in range(q):
	l, r, k = list(map(int, input().split()))
	if k >  r - l + 1:
		print("Out of range")
	else:
		hl = [h[r][i] - h[l-1][i] for i in range(26)]
		for i in range(26):
			k -= hl[i]
			if k <= 0:
				print(chr(i + A))
				break


N, Q = list(map(int, input().split()))
N = N + 1
S = '0' + input()

P = [[0] * 26 for i in range(N)]
for i in range(1, N):
	d = ord(S[i]) - ord('a')
	for j in range(26):
		if j == d:
			P[i][j] = P[i - 1][j] + 1
		else:
			P[i][j] = P[i - 1][j]


for _ in range(Q):
	L, R, K = list(map(int, input().split()))
	Kthsmall, j = 0, 0

	while j < 26:
		Kthsmall += P[R][j] - P[L - 1][j]
		if Kthsmall >= K:
			break
		j += 1
	ans = chr(97 + j)
	if j == 26:
		print('Out of range')
	else:
		print(ans)