Simplified Input Method

This problem involves a simplified input method that initially has a dictionary \(U\) of words. When a user inputs a string \(s\) and an integer \(x\), the input method processes the query as follows:

Let \(a\) be the number of words \(s_i \in U\) for which \(s\) is a prefix (i.e. \(s\) is a prefix of \(s_i\)). Then:

• If \(a \ge x\), sort all matching words in descending order by their output frequency (the number of times they have been output) and, as a tiebreaker, in lexicographical ascending order. Output the \(x\text{-th}\) word in this ordering and increase its output frequency by 1.
• If \(0 < a < x\), output the last word in the sorted order (using the same sorting criteria) and increase its output frequency by 1.
• If \(a = 0\), output 404Error.

Note: The frequency counts of all words are initially 0 and are updated as queries are processed.

Input Format: The first line contains an integer \(n\) representing the number of words in the dictionary \(U\). The next \(n\) lines each contain a word. The following line contains an integer \(q\) denoting the number of queries. Each of the next \(q\) lines contains a string \(s\) and an integer \(x\), separated by space.

inputFormat

The input begins with an integer \(n\) (\(1 \le n \le 1000\)), representing the number of words in the dictionary \(U\). The next \(n\) lines each contain a word (consisting of lowercase letters only). Then an integer \(q\) (\(1 \le q \le 1000\)) is given, followed by \(q\) queries. Each query is given as a string \(s\) and an integer \(x\) (\(x \ge 1\)) separated by a space. The string \(s\) is the prefix used for matching words in the dictionary.

outputFormat

For each query, output a single line containing the resulting word as described below:

• If there are at least \(x\) words in \(U\) which have \(s\) as a prefix, output the \(x\text{-th}\) word from the sorted list (sorted primarily by descending output frequency, and secondarily by lexicographical order ascending), then increase its frequency count by 1.
• If the number of matching words is greater than 0 but less than \(x\), output the last word in the sorted list, then increase its frequency count by 1.
• If no word in \(U\) has \(s\) as a prefix, output 404Error.

sample

4
hello
hell
heaven
goodbye
3
he 2
g 1
ha 1

hell
goodbye
404Error