Description

This simple input method originally has a dictionary $\text{U}$. When the user types, the input method reads a string $s$ and an integer $x$ from the user. For this string, there are several cases:

Let the number of words $s_i \in \text{U}$ such that $s$ is a prefix of $s_i$ be $a$.

• When $a \ge x$, output the $x$-th $s_i$ after sorting by output count in descending order as the first key and lexicographical order as the second key, and then increase its output count by $1$.
• When $x > a > 0$, output the last $s_i$ after sorting by output count in descending order as the first key and lexicographical order as the second key, and then increase its output count by $1$.
• When $a = 0$, output 404Error.

Input Format

Line $1$ contains an integer $n$, representing that there are originally $n$ words in $\text{U}$. The initial output count of every originally existing word is $0$.

Lines $2$ to $n+1$ each contain a string $str$, representing a word that originally exists in the dictionary.

Line $n+2$ contains an integer $m$, representing that the user performs $m$ operations.

Lines $n+3$ to $n+m+2$ each contain a string $s$ and an integer $x$, whose meanings are described above.

Output Format

For each of the user’s $1$ operation, output a string.

3
fan
fantasy
father
6
fat 1
fa 1
fan 1
fan 1
fa 1
fant 1

father
father
fan
fan
fan
fantasy

5
uva
usaco
usa
usssu
konjac
11
u 2
u 2
kkk 1
uv 2
us 3
u 4
u 1
u 2
k 1
u 3
usa 1

usaco
usa
404Error
uva
usssu
uva
uva
usa
konjac
usaco
usa

Hint

Sample Explanation

Sample Explanation 1

There is only $1$ word with prefix fat, so output father, and increase its output count by $1$.
For prefix fa, the word with the highest output count is father, so output it, and increase its output count by $1$.
For prefix fan, all output counts are $0$, but fan is the smallest in lexicographical order, so output it, and increase its output count by $1$.
For prefix fan, the word with the highest output count is fan, so output fan, and increase its output count by $1$.
For prefix fa, the word with the highest output count is fan, so output it, and increase its output count by $1$.
There is only one word with prefix fant, which is fantasy, so output it, and increase its output count by $1$.

Constraints

For $100\%$ of the testdata, $|s|,|str|\le10,1\leq x\le10^4$, and all letters are lowercase letters.

Translated by ChatGPT 5