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
• bbbbb
• ccccc
• ddddd
• eeeee
• 3
• 3 3 3
• 1 5 16
• 3 5 15

Sample Output

• c
• d
• e

Explanation

• Q1 Grouped String — ccccc. 3rd character is c
• Q2 Grouped String — aaaaabbbbbcccccdddddeeeee. 16th character is d
• Q3 Grouped String — cccccdddddeeeee. 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)