← 返回题目列表

Codeforces · 883/E

E. 奇迹之地

中文机器翻译题面 查看原题

波利卡普斯参加电视节目“奇迹之地”。表演的参与者必须尽快猜出隐藏的单词。最初,该单词的所有字母都被隐藏。

游戏由几个回合组成。每次参与者都会说出一个字母,电视节目主持人会回答单词中是否有这样的字母。如果有这样的字母,那么主持人就会透露所有这样的字母。例如,如果隐藏的单词是“abacaba”,玩家说出字母“a”,则主持人将显示“a”占据的所有位置的字母:1、3、5和7(位置从1开始从左到右编号)。

Polycarpus 知道 m 个与隐藏单词长度完全相同的单词。隐藏的单词也是他所知道的,并且作为这 m 个单词之一出现。

目前已经进行了许多回合,并且隐藏单词的一些字母(可能是零)已经被揭示。此前波利卡普已经准确地讲述了目前透露的信件。

轮到波利卡普斯了。他要以这样的方式讲述一封信,电视节目主持人肯定会再透露至少一封信。波利卡普斯无法说出那些已经被揭示的字母。

你的任务是帮助Polycarpus,找出他能说出的字母数量,以便节目主持人至少能说出剩余字母中的至少一个。

输入

第一行包含一个整数 n (1 ≤ n ≤ 50) — 隐藏字的长度。

下面一行描述了已经透露的字母。它包含长度为n的字符串,该字符串由小写拉丁字母和符号“*”组成。如果某个位置有一封信,那么这封信就已经被揭露了。如果该位置含有符号“*”,则说明该位置的字母尚未显露。可以保证至少有一封信尚未结案。

第三行包含一个整数 m (1 ≤ m ≤ 1000) — Polycarpus 知道的长度为 n 的单词数。接下来的 m 行包含单词本身——由小写拉丁字母组成的 n 个字母字符串。所有的词都是不同的。

保证隐藏单词出现为给定的 m 个单词之一。在采取当前行动之前,波利卡普已经准确地讲述了目前所透露的信件。

输出

输出单个整数——Polycarpus 可以说出的字母数量,以便电视节目主持人肯定至少再透露一个字母。这个数字有可能为零。

示例

输入 #1

4
a**d
2
abcd
acbd

输出 #1

2

输入 #2

5
lo*er
2
lover
loser

输出 #2

0

输入 #3

3
a*a
2
aaa
aba

输出 #3

1

注意

在第一个示例中,Polycarpus 可以说出字母“b”和“c”,这肯定会被揭示。

第二个例子不包含任何字母,因为不清楚,字母“v”或“s”中的哪一个位于隐藏单词的第三个位置。

在第三个例子中,Polycarpus 确切地知道隐藏的单词是“aba”,因为如果它是“aaa”,那么第二个字母“a”在之前的一轮中就已经被揭示了。