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”。
输入
输入的第一行包含整数 $$$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$$$ 字符之间(含)。它仅包含小写拉丁字母、数字和点字符 ('.')。
输出
打印 $$$q$$$ 行,每个查询一行。第 $$$j$$$ 行应包含第 $$$j$$$ 查询的响应 — 两个值 $$$c_j$$$ 和 $$$t_j$$$,其中
- $$$c_j$$$ 是第 $$$j$$$ 查询的匹配文件数,
- $$$t_j$$$ 是与第 $$$j$$$ 个查询匹配的任何文件的名称。如果没有这样的文件,则打印单个字符“-”。如果有多个匹配的文件,则打印其中一个。
示例
输入 #1
4 test contests test. .test 6 ts . st. .test contes. st
输出 #1
1 contests 2 .test 1 test. 1 .test 0 - 4 test.