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".
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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st
|
1 contests
2 .test
1 test.
1 .test
0 -
4 test.
|