#D4578. BerOS File Suggestion
BerOS File Suggestion
BerOS File Suggestion
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, ..., 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".
Input
The first line of the input contains integer n (1 ≤ n ≤ 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 ≤ q ≤ 50000) — the total number of queries.
The following q lines contain queries s_1, s_2, ..., 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 ('.').
Output
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.
Example
Input
4 test contests test. .test 6 ts . st. .test contes. st
Output
1 contests 2 .test 1 test. 1 .test 0 - 4 test.
inputFormat
Input
The first line of the input contains integer n (1 ≤ n ≤ 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 ≤ q ≤ 50000) — the total number of queries.
The following q lines contain queries s_1, s_2, ..., 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 ('.').
outputFormat
Output
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.
Example
Input
4 test contests test. .test 6 ts . st. .test contes. st
Output
1 contests 2 .test 1 test. 1 .test 0 - 4 test.
样例
4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st
1 contests
2 .test
1 test.
1 .test
0 -
4 .test