BerOS File Suggestion

题意翻译

开始给你$n$个由小写字母、数字、以及`'.'`（点号）构成的字符串$(n\le 10000,len\le 8)$，后有$q(q\le 50000)$组询问，询问上述字符串中有多少串中包含给出字符串的子串，并输出其中的任意一个串。如果不存在输出`0 -`。

题目描述

Polycarp is working on a new operating system called BerOS. He asks you to help with implementation of a file suggestion feature. There are $ n $ files on hard drive and their names are $ f_1, f_2, \dots, f_n $ . Any file name contains between $ 1 $ and $ 8 $ characters, inclusive. All file names are unique. The file suggestion feature handles queries, each represented by a string $ s $ . For each query $ s $ it should count number of files containing $ s $ as a substring (i.e. some continuous segment of characters in a file name equals $ s $ ) and suggest any such file name. For example, if file names are "read.me", "hosts", "ops", and "beros.18", and the query is "os", the number of matched files is $ 2 $ (two file names contain "os" as a substring) and suggested file name can be either "hosts" or "beros.18".

输入输出格式

输入格式

The first line of the input contains integer $ n $ ( $ 1 \le n \le 10000 $ ) — the total number of files. The following $ n $ lines contain file names, one per line. The $ i $ -th line contains $ f_i $ — the name of the $ i $ -th file. Each file name contains between $ 1 $ and $ 8 $ characters, inclusive. File names contain only lowercase Latin letters, digits and dot characters ('.'). Any sequence of valid characters can be a file name (for example, in BerOS ".", ".." and "..." are valid file names). All file names are unique. The following line contains integer $ q $ ( $ 1 \le q \le 50000 $ ) — the total number of queries. The following $ q $ lines contain queries $ s_1, s_2, \dots, s_q $ , one per line. Each $ s_j $ has length between $ 1 $ and $ 8 $ characters, inclusive. It contains only lowercase Latin letters, digits and dot characters ('.').

输出格式

Print $ q $ lines, one per query. The $ j $ -th line should contain the response on the $ j $ -th query — two values $ c_j $ and $ t_j $ , where - $ c_j $ is the number of matched files for the $ j $ -th query, - $ t_j $ is the name of any file matched by the $ j $ -th query. If there is no such file, print a single character '-' instead. If there are multiple matched files, print any.

输入输出样例

输入样例 #1

4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st

输出样例 #1

1 contests
2 .test
1 test.
1 .test
0 -
4 test.