题目描述

在一片神秘的魔法大陆上，有一个被称为“语言之塔”的地方。这座塔由古老的符文大师建造，传说中蕴含着掌控语言和文字的终极力量。然而，这种力量并非轻易可得，进入塔中试炼的人必须完成一道道精妙的文字谜题，才能解锁语言之塔的秘密。

阿兔是一位年轻的魔法学徒，她热衷于探索语言的奥秘。这一天，她接到了语言之塔的邀请，来到塔中接受试炼。塔中的第一关是一个简单但复杂的任务：

• “在这篇文章中找到所有以字符 $t$ 开头或结尾的单词，并告诉我它们一共出现了几次。”

文章中有 $n$ 个单词，阿兔需要回答 $q$ 个问题，每个问题都要求她迅速计算出满足条件的单词出现的次数。

“记住，阿兔，”塔灵低声说道，“语言的力量在于细节，任何一个前后缀都可能隐藏着真理的碎片。”

输入格式

第一行包含两个正整数 $n,q \ (1\leq n,q \leq 2*10^{5})$，分别表示单词个数和询问次数。

第二行包含 $n$ 个字符串 $s$ ，表示文章内的单词。

第三行包含 $q$ 个字符串 $t$ ，表问每次询问的单词。

每个单词用空格分开，单词仅包含小写字母，文章内的字符串总长度不超过 $10^{6}$，询问的字符串总长度不超过 $10^{6}$。

输出格式

请输出 $q$ 行，每行包含一个整数，以字符 $t$ 开头或结尾的单词出现次数。

5 4
zimeatuer love hanhanzime love zimeycj
zime atuer lov icefrost

3
1
2
0