{"raw_statement":[{"iden":"statement","content":"Polycarpus takes part in the \"Field of Wonders\" TV show. The participants of the show have to guess a hidden word as fast as possible. Initially all the letters of the word are hidden.\n\nThe game consists of several turns. At each turn the participant tells a letter and the TV show host responds if there is such letter in the word or not. If there is such letter then the host reveals **all** such letters. For example, if the hidden word is \"_abacaba_\" and the player tells the letter \"_a_\", the host will reveal letters at all positions, occupied by \"_a_\": 1, 3, 5 and 7 (positions are numbered from left to right starting from 1).\n\nPolycarpus knows _m_ words of exactly the same length as the hidden word. The hidden word is also known to him and appears as one of these _m_ words.\n\nAt current moment a number of turns have already been made and some letters (possibly zero) of the hidden word are already revealed. Previously Polycarp has told exactly the letters which are currently revealed.\n\nIt is Polycarpus' turn. He wants to tell a letter in such a way, that the TV show host will assuredly reveal at least one more letter. Polycarpus cannot tell the letters, which are already revealed.\n\nYour task is to help Polycarpus and find out the number of letters he can tell so that the show host will assuredly reveal at least one of the remaining letters."},{"iden":"input","content":"The first line contains one integer _n_ (1 ≤ _n_ ≤ 50) — the length of the hidden word.\n\nThe following line describes already revealed letters. It contains the string of length _n_, which consists of lowercase Latin letters and symbols \"_*_\". If there is a letter at some position, then this letter was already revealed. If the position contains symbol \"_*_\", then the letter at this position has not been revealed yet. It is guaranteed, that at least one letter is still closed.\n\nThe third line contains an integer _m_ (1 ≤ _m_ ≤ 1000) — the number of words of length _n_, which Polycarpus knows. The following _m_ lines contain the words themselves — _n_\\-letter strings of lowercase Latin letters. All words are distinct.\n\nIt is guaranteed that the hidden word appears as one of the given _m_ words. Before the current move Polycarp has told exactly the letters which are currently revealed."},{"iden":"output","content":"Output the single integer — the number of letters Polycarpus can tell so that the TV show host definitely reveals at least one more letter. It is possible that this number is zero."},{"iden":"examples","content":"Input\n\n4\na**d\n2\nabcd\nacbd\n\nOutput\n\n2\n\nInput\n\n5\nlo*er\n2\nlover\nloser\n\nOutput\n\n0\n\nInput\n\n3\na*a\n2\naaa\naba\n\nOutput\n\n1"},{"iden":"note","content":"In the first example Polycarpus can tell letters \"_b_\" and \"_c_\", which assuredly will be revealed.\n\nThe second example contains no letters which can be told as it is not clear, which of the letters \"_v_\" or \"_s_\" is located at the third position of the hidden word.\n\nIn the third example Polycarpus exactly knows that the hidden word is \"_aba_\", because in case it was \"_aaa_\", then the second letter \"_a_\" would have already been revealed in one of previous turns."}],"translated_statement":[{"iden":"statement","content":"Polycarpus 参加电视节目《奇妙领域》。参赛者需要尽可能快地猜出一个隐藏的单词。最初，单词的所有字母都是隐藏的。\n\n游戏包含若干轮。每轮中，参赛者说出一个字母，电视节目主持人会回应该字母是否存在于单词中。如果存在，主持人会揭示该字母在单词中出现的 *所有* 位置。例如，如果隐藏单词是 \"_abacaba_\"，而玩家说出字母 \"_a_\"，则主持人会揭示所有包含 \"_a_\" 的位置：#cf_span[1], #cf_span[3], #cf_span[5] 和 #cf_span[7]（位置从左到右从 1 开始编号）。\n\nPolycarpus 知道 #cf_span[m] 个与隐藏单词长度完全相同的单词。他也知道隐藏单词就是这 #cf_span[m] 个单词中的一个。\n\n目前，已经进行了若干轮，隐藏单词的某些字母（可能为零）已被揭示。在此之前，Polycarp 已经说出的字母恰好就是当前已被揭示的那些字母。\n\n现在轮到 Polycarpus 发言。他希望说出一个字母，使得电视节目主持人 *必然* 揭示至少一个额外的字母。Polycarpus 不能说出已经被揭示的字母。\n\n你的任务是帮助 Polycarpus，找出他能说出的、使得主持人必然揭示至少一个剩余字母的字母数量。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 50]）——隐藏单词的长度。\n\n接下来的一行描述了已揭示的字母。它是一个长度为 #cf_span[n] 的字符串，由小写拉丁字母和符号 \"_*_\" 组成。如果某个位置是字母，则该字母已被揭示；如果该位置是符号 \"_*_\"，则该位置的字母尚未被揭示。保证至少有一个字母仍未被揭示。\n\n第三行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 1000]）——Polycarpus 知道的长度为 #cf_span[n] 的单词数量。接下来的 #cf_span[m] 行是这些单词本身——每个都是由小写拉丁字母组成的 #cf_span[n] 个字母的字符串。所有单词互不相同。\n\n保证隐藏单词是给定的 #cf_span[m] 个单词中的一个。在当前轮次之前，Polycarp 已经说出了所有当前已被揭示的字母。\n\n输出一个整数——Polycarpus 可以说出的、使得主持人必然揭示至少一个额外字母的字母数量。这个数量可能是零。\n\n在第一个例子中，Polycarpus 可以说出字母 \"_b_\" 和 \"_c_\"，它们必然会被揭示。\n\n第二个例子中没有可以安全说出的字母，因为无法确定隐藏单词第三个位置是 \"_v_\" 还是 \"_s_\"。\n\n在第三个例子中，Polycarpus 确定隐藏单词是 \"_aba_\"，因为如果它是 \"_aaa_\"，那么第二个字母 \"_a_\" 就会在之前的某一轮中被揭示了。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 50]）——隐藏单词的长度。接下来的一行描述了已揭示的字母。它是一个长度为 #cf_span[n] 的字符串，由小写拉丁字母和符号 \"_*_\" 组成。如果某个位置是字母，则该字母已被揭示；如果该位置是符号 \"_*_\"，则该位置的字母尚未被揭示。保证至少有一个字母仍未被揭示。第三行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 1000]）——Polycarpus 知道的长度为 #cf_span[n] 的单词数量。接下来的 #cf_span[m] 行是这些单词本身——每个都是由小写拉丁字母组成的 #cf_span[n] 个字母的字符串。所有单词互不相同。保证隐藏单词是给定的 #cf_span[m] 个单词中的一个。在当前轮次之前，Polycarp 已经说出了所有当前已被揭示的字母。"},{"iden":"output","content":"输出一个整数——Polycarpus 可以说出的、使得主持人必然揭示至少一个额外字母的字母数量。这个数量可能是零。"},{"iden":"examples","content":"输入4a**d2abcdacbd输出2输入5lo*er2loverloser输出0输入3a*a2aaaaba输出1"},{"iden":"note","content":"在第一个例子中，Polycarpus 可以说出字母 \"_b_\" 和 \"_c_\"，它们必然会被揭示。第二个例子中没有可以安全说出的字母，因为无法确定隐藏单词第三个位置是 \"_v_\" 还是 \"_s_\"。在第三个例子中，Polycarpus 确定隐藏单词是 \"_aba_\"，因为如果它是 \"_aaa_\"，那么第二个字母 \"_a_\" 就会在之前的某一轮中被揭示了。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the hidden word.  \nLet $ S \\in \\{a,\\dots,z,\\_\\}^n $ be the current state string, where $ S_i \\in \\{a,\\dots,z\\} $ if letter at position $ i $ is revealed, and $ S_i = \\_ $ if hidden.  \nLet $ M = \\{w_1, \\dots, w_m\\} $ be a set of $ m $ candidate words, each $ w_j \\in \\{a,\\dots,z\\}^n $, all of length $ n $, distinct, and guaranteed to include the hidden word.  \n\nLet $ R \\subseteq \\{a,\\dots,z\\} $ be the set of already revealed letters:  \n$ R = \\{ S_i \\mid S_i \\neq \\_ \\} $.  \n\nLet $ H \\subseteq \\{1, \\dots, n\\} $ be the set of hidden positions:  \n$ H = \\{ i \\mid S_i = \\_ \\} $.  \n\nLet $ C \\subseteq M $ be the set of candidate words consistent with $ S $:  \n$ C = \\{ w \\in M \\mid \\forall i \\in \\{1,\\dots,n\\},\\ S_i \\neq \\_ \\Rightarrow w_i = S_i \\} $.  \n\nLet $ L \\subseteq \\{a,\\dots,z\\} \\setminus R $ be the set of letters not yet revealed.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 50 $  \n2. $ 1 \\le m \\le 1000 $  \n3. $ |H| \\ge 1 $  \n4. $ C \\neq \\emptyset $ and the true hidden word $ \\in C $  \n5. All words in $ M $ have length $ n $, consist of lowercase Latin letters, and are distinct.  \n\n**Objective**  \nCompute the number of letters $ \\ell \\in L $ such that:  \n$ \\forall w \\in C,\\ \\exists i \\in H \\text{ such that } w_i = \\ell $.  \n\nThat is, the letter $ \\ell $ appears in **every** consistent candidate word at **some** hidden position.","simple_statement":null,"has_page_source":false}