Autocomplete

Problem Description:

Given a list of dictionary words and a list of queries, your task is to implement an autocomplete feature. For each query string, output all dictionary words that begin with the query, in lexicographical order. If a query string is empty, output all dictionary words.

For example, if the dictionary is [apple, application, apricot, banana, berry, cherry, date] and the query is app, then the output should be apple application.

Mathematically, for a query (q) and dictionary (D), you need to determine the set
[ {w \in D : w \text{ starts with } q}] ]

It is recommended to sort the dictionary and then perform prefix matching for each query. If no words match the query, output an empty line.

inputFormat

Input is read from standard input (stdin) in the following format:

1. The first line contains an integer (n) representing the number of dictionary words.
2. The second line contains (n) space-separated words, the dictionary.
3. The third line contains an integer (m) representing the number of queries.
4. The next (m) lines each contain a query string. (A query string may be empty, in which case all dictionary words should be output.)

outputFormat

For each query, output a single line to standard output (stdout) containing all matching dictionary words separated by a single space, in lexicographical order. If no words match a query, output an empty line.## sample

7
apple application apricot banana berry cherry date
4
app
ban
ca
z

apple application
banana