背景

题目描述

你躲在灯后，静静地听着 Sans の 奇妙双关。

Sans 一共说了 \(n\) 个双关。现在有 \(m\) 个已知单词与它们的读音。

1.若一个词是另一个词的子串，则两个词存在双关联系。

2.如果两个词读音完全相同，则两个词存在双关联系。

3.如果 A 与 B 存在双关联系，B 与 C 存在双关联系，那么 A 与 C 存在双关联系。

每次 Sans 将给出一个单词，请输出有多少种可能的双关联系：

输入格式

第一行两个正整数，\(n\) 和 \(m\)。

第二行到第 \(m+1\) 行，每行两个字符串，表示第 i 个单词与发音。

第 \(m+2\) 行到第 \(m+n+1\) 行，每行一个字符串，表示 Sans 所说的单词。

输出格式

一共 \(n\) 行，每行一个非负整数，表示对于 Sans 说的第 i 个单词，可能的双关联系数量。

样例

输入#1

1 2
skeleton skeleton
ton ton
ton

输出#1

1

输入#2

3 3
bone a
ww a
bon b
bone
ww
bon

输出#2

2
2
2

输入#3

3 7
sans a
san b
papyrus c
undyne a
rus d
chenpengda e
chenpengda1 f
sans
papyrus
chenpengda

输出#3

2
1
1

说明

样例 1 说明：skeleton 与 ton 发音不同，但是 ton 是 skeleton 的子串，所以两者之间有双关联系，输出 1

Sans 只会说已知单词中的词，且不会说他已经说过的词。

没有任意两个已知单词的字符完全相同（读音可能相同）。

可能的双关联系的词不能和 Sans 给的词一样。

数据范围

输入中的所有字符串均由大写字母与小写字母组成，长度不超过 100。

数据点编号	数据范围
\(1,2,3\)	\(n=5,m=10\)
\(4,5\)	\(n=50,m=100\)
\(6,7\)	\(n=200,m=500\)
\(8,9\)	\(n=500,m=1000\)
\(10\)	\(n=800,m=1000\)