Given a list that contains N strings of lowercase English alphabets. Any number of contiguous strings can be found together to form a new string. The grouping function accepts two integers X and Y and concatenates all strings between indices X and Y (inclusive) and returns a modified string in which the alphabets of the concatenated string are sorted.
You are asked Q questions each containing two integers L and R. Determine the K th. character in the concatenated string if we pass L and R to the grouping function.
Note: It is always guaranteed that the Kth position is valid
Input Format
- First Line: N(number of strings in the list)
- Next N lines: String s_i
- Next line Q(number of questions)
- Next Q lines : Three space-separated integers L, R and K
Output Format
For each question, print the K th character of the concatenated string in a new line.
Sample Test Cases
Sample Input
- 5
- aaaaa
- bbbb
- cccccd
- eeeee
- ddddd
- 3
- 3 3 3
- 1 5 16
- 3 5 15
Sample Output
- c
- d
- e
Explanation
- Q1 Grouped String cccccd. 3rd character is c
- Q2 Grouped String aaaaabbbbcccccddddddeeeee. 16th character is d
- Q3 Grouped String cccccddddddeeeee. 15th character is e
Input
- 5
- zpqrs
- efghi
- jklmn
- abcde
- 2
- 3 3 3
- 1 5 6
Output
- g
- f
Solution of this problem with complexity O(NQ) is trivial. Is it possible to solve this question with complexity better than O(NQ)