C. Suffixes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$n$$$ dictionary words and $$$q$$$ questions, for each question, answer the following:

  • Read $$$s$$$ the question word.
  • Read the integer $$$k$$$.
  • Find all the dictionary words that have a common suffix with the question word.
  • Among the dictionary words that have a common suffix with the question word, select the ones that contain the longest common suffix.
  • Sort lexicographically the selected words.
  • Select the word that is in the $$$k-$$$th position.
  • Print the position of the selected word relative to to the original order of the dictionary words.
  • If there are fewer than $$$k$$$ words with the longest common suffix, print $$$-1$$$.
Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^5)-$$$ the number of dictionary words.

Each of the following $$$n$$$ lines contains a word $$$d_i$$$ $$$(1 \le |d_i| \le 5; 1 \le i \le n)$$$, consisting of lowercase Latin letters, and it is guaranteed that all these words are distinct from each other.

The next line contains an integer $$$q$$$ $$$(1 \le 10^5)-$$$ the number of questions.

Each of the following $$$q$$$ lines contains the information of each question, a word $$$s_i$$$ composed of lowercase Latin letters and an integer $$$k_i$$$ $$$(1 \le |s_i| \le 5; 1 \le k_i \le 10^5; 1 \le i \le q)$$$.

It is guaranteed that the total size of the dictionary words does not exceed $$$5*10^5$$$. Similarly, it is guaranteed that the total size of the question words does not exceed $$$5*10^5$$$.

Output

For each question, print the answer.

Example
Input
4
vaca
baca
hola
abola
6
a 1
a 3
a 4
a 5
lola 2
ahaca 1
Output
4
3
1
-1
3
2