Question

Sheokand loves strings. Chef has N strings S1,S2,…,SN which he wants to give to Sheokand; however, he doesn't want to give them away for free, so Sheokand must first correctly answer Q queries Chef asks him. In each query, Chef tells Sheokand an integer R and a string P. Consider Chef's strings S1 through SR. Out of these strings, consider all strings such that their longest common prefix with P is maximum possible. Sheokand should find the lexicographically smallest of these strings.

Answer 1

hi she no pata you can take help of google

Answer 2

Answer:

Lexicographically smallest of these strings are given below:

abcd

abcdex

abcde

Explanation:

Input

• The first line of the input contains a single integer N.
• N lines follow. For each valid i, the i-th of these lines contains Chef's string Si.
• The next line contains a single integer Q.
• The following Q lines describe queries. Each of these lines contains an interger R, followed by a space and a string P.

Output

• For each query, print a single line containing the string that satisfies the required conditions — the answer to that query.

Constraints

1≤N≤100,000

1≤|Si|≤10 for each valid i

1≤Q≤100,000

1≤R≤N

1≤|P|≤10

Subtasks

Subtask #1 (30 points): 1≤N,R≤1,000

Subtask #2 (70 points): original constraints

Example Input

4

abcd

abce

abcdex

abcde

3

3 abcy

3 abcde

4 abcde

Example Output

abcd

abcdex

abcde

Explanation

• Query 1: For strings S1 through S3, the longest common prefix is always "abc", but "abcd" is the lexicographically smallest of these three strings.
• Query 2: For strings S1 through S3, the longest common prefix with maximum length is "abcde" and the only string for which it is the LCP is "abcdex", so this is the answer.
• Query 3: For strings S1 through S4, the longest common prefix with maximum length is "abcde"; it is the LCP for strings "abcdex" and "abcde", but "abcde" is the lexicographically smaller string, so it is the answer.
• Let: s1 be the string smaller than the largest string of the target string
• s2 is the smallest string greater than or equal to the target string
• For a string set, the string with the longest common prefix of the target string must be s1 or s2.
• Considering that the string to be output is the string with the smallest lexicographic order, if it is s2, just output it directly. If it is s1, then the longest common prefix in front of s1 may be the same length, but the string with a smaller lexicographic order, but at most, it will not be More than 25, just enumerate. According to the meaning of the question, it is not difficult to think of sorting the r in queries, and gradually inserting the strings into the set in order. For each query, use lower_bound to complete the search within a logn time, and then use up to 25 enumerations to find the answer string.