CF1070H.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, \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".

Polycarp 正在开发一款名为 BerOS 的新操作系统。他请你协助实现文件建议功能。

硬盘上共有 $n$ 个文件，其文件名分别为 $f_1, f_2, \dots, f_n$。任意文件名的长度均为 $1$ 至 $8$ 个字符（含端点）。所有文件名互不相同。

文件建议功能需处理若干查询，每个查询由一个字符串 $s$ 表示。对于每个查询 $s$，该功能应统计包含 $s$ 作为子串（即文件名中存在一段连续的字符恰好等于 $s$）的文件数量，并从中任选一个满足条件的文件名作为建议结果。

例如，若文件名集合为 "read.me"、"hosts"、"ops" 和 "beros.18"，而查询字符串为 "os"，则匹配的文件数量为 $2$（有两个文件名包含子串 "os"），建议的文件名可以是 "hosts" 或 "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 ('.').

输入的第一行包含一个整数 $n$（$1 \le n \le 10000$）—— 文件总数。

接下来的 $n$ 行每行包含一个文件名。第 $i$ 行包含 $f_i$ —— 第 $i$ 个文件的文件名。每个文件名长度为 $1$ 至 $8$ 个字符（含端点）。文件名仅由小写拉丁字母、数字和点号字符（'.'）组成。任意由有效字符组成的序列均可作为文件名（例如，在 BerOS 系统中，"."、".." 和 "..." 均为合法的文件名）。所有文件名互不相同。

接下来一行包含一个整数 $q$（$1 \le q \le 50000$）—— 查询总数。

接下来的 $q$ 行每行包含一个查询字符串 $s_1, s_2, \dots, s_q$。每个 $s_j$ 的长度为 $1$ 至 $8$ 个字符（含端点），且仅由小写拉丁字母、数字和点号字符（'.'）组成。

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.

输出 $q$ 行，每行对应一个查询。第 $j$ 行应包含对第 $j$ 个查询的响应——两个值 $c_j$ 和 $t_j$，其中：

• $c_j$ 表示与第 $j$ 个查询匹配的文件数量；
• $t_j$ 表示任意一个与第 $j$ 个查询匹配的文件名。若不存在这样的文件，则输出单个字符 \-；若存在多个匹配文件，则任选其一输出。