{"problem":{"name":"C. Shockers","description":{"content":"Valentin participates in a show called \"Shockers\". The rules are quite easy: jury selects one letter which Valentin doesn't know. He should make a small speech, but every time he pronounces a word tha","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF907C"},"statements":[{"statement_type":"Markdown","content":"Valentin participates in a show called \"Shockers\". The rules are quite easy: jury selects one letter which Valentin doesn't know. He should make a small speech, but every time he pronounces a word that contains the selected letter, he receives an electric shock. He can make guesses which letter is selected, but for each incorrect guess he receives an electric shock too. The show ends when Valentin guesses the selected letter correctly.\n\nValentin can't keep in mind everything, so he could guess the selected letter much later than it can be uniquely determined and get excessive electric shocks. Excessive electric shocks are those which Valentin got after the moment the selected letter can be uniquely determined. You should find out the number of excessive electric shocks.\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 105) — the number of actions Valentin did.\n\nThe next _n_ lines contain descriptions of his actions, each line contains description of one action. Each action can be of one of three types:\n\n1.  Valentin pronounced some word and didn't get an electric shock. This action is described by the string \"_. w_\" (without quotes), in which \"_._\" is a dot (ASCII-code 46), and _w_ is the word that Valentin said.\n2.  Valentin pronounced some word and got an electric shock. This action is described by the string \"_! w_\" (without quotes), in which \"_!_\" is an exclamation mark (ASCII-code 33), and _w_ is the word that Valentin said.\n3.  Valentin made a guess about the selected letter. This action is described by the string \"_? s_\" (without quotes), in which \"_?_\" is a question mark (ASCII-code 63), and _s_ is the guess — a lowercase English letter.\n\nAll words consist only of lowercase English letters. The total length of all words does not exceed 105.\n\nIt is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action. Moreover, it's guaranteed that if Valentin got an electric shock after pronouncing some word, then it contains the selected letter; and also if Valentin didn't get an electric shock after pronouncing some word, then it does not contain the selected letter.\n\n## Output\n\nOutput a single integer — the number of electric shocks that Valentin could have avoided if he had told the selected letter just after it became uniquely determined.\n\n[samples]\n\n## Note\n\nIn the first test case after the first action it becomes clear that the selected letter is one of the following: _a_, _b_, _c_. After the second action we can note that the selected letter is not _a_. Valentin tells word \"b\" and doesn't get a shock. After that it is clear that the selected letter is _c_, but Valentin pronounces the word _cd_ and gets an excessive electric shock.\n\nIn the second test case after the first two electric shocks we understand that the selected letter is _e_ or _o_. Valentin tries some words consisting of these letters and after the second word it's clear that the selected letter is _e_, but Valentin makes 3 more actions before he makes a correct hypothesis.\n\nIn the third example the selected letter can be uniquely determined only when Valentin guesses it, so he didn't get excessive electric shocks.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Valentin 参加了一个名为 \"Shockers\" 的节目。规则很简单：评委选定一个 Valentin 不知道的字母。他需要发表一段简短的演讲，但每次他说出包含该选定字母的单词时，都会受到电击。他可以猜测选定的字母是什么，但每次错误的猜测也会导致电击。当 Valentin 正确猜出选定字母时，节目结束。\n\nValentin 无法记住所有信息，因此他可能在选定字母已经可以唯一确定很久之后才做出猜测，从而遭受过多的电击。过多的电击是指在选定字母已经可以唯一确定之后，Valentin 所遭受的电击。你需要计算出这些过多的电击数量。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— Valentin 执行的动作数量。\n\n接下来的 #cf_span[n] 行描述了他的每个动作，每行描述一个动作。每个动作可以是以下三种类型之一：\n\n所有单词仅由小写英文字母组成。所有单词的总长度不超过 #cf_span[105]。\n\n保证最后一个动作是关于选定字母的猜测。同时保证在最后一个动作之前，Valentin 没有做出过正确的猜测。此外，保证如果 Valentin 在说出某个单词后受到电击，则该单词包含选定字母；如果他没有受到电击，则该单词不包含选定字母。\n\n请输出一个整数——如果 Valentin 在选定字母刚能被唯一确定时立即说出该字母，他本可以避免的电击次数。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— Valentin 执行的动作数量。接下来的 #cf_span[n] 行描述了他的每个动作，每行描述一个动作。每个动作可以是以下三种类型之一：\n\nValentin 说出某个单词但未受到电击。此动作由字符串 \"_. w_\"（不含引号）描述，其中 \"_._\" 是一个点（ASCII 码 46），#cf_span[w] 是 Valentin 说出的单词。\n\nValentin 说出某个单词并受到电击。此动作由字符串 \"_! w_\"（不含引号）描述，其中 \"_!_\" 是一个感叹号（ASCII 码 33），#cf_span[w] 是 Valentin 说出的单词。\n\nValentin 对选定字母做出猜测。此动作由字符串 \"_? s_\"（不含引号）描述，其中 \"_?_\" 是一个问号（ASCII 码 63），#cf_span[s] 是他的猜测——一个小写英文字母。\n\n所有单词仅由小写英文字母组成。所有单词的总长度不超过 #cf_span[105]。\n\n保证最后一个动作是关于选定字母的猜测。同时保证在最后一个动作之前，Valentin 没有做出过正确的猜测。此外，保证如果 Valentin 在说出某个单词后受到电击，则该单词包含选定字母；如果他没有受到电击，则该单词不包含选定字母。\n\n## Output\n\n输出一个整数——如果 Valentin 在选定字母刚能被唯一确定时立即说出该字母，他本可以避免的电击次数。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，第一次动作后可以确定选定字母是以下之一：#cf_span[a, b, c]。第二次动作后我们可以确定选定字母不是 #cf_span[a]。Valentin 说出单词 \"b\" 并未受到电击。此后可以确定选定字母是 #cf_span[c]，但 Valentin 说出了单词 #cf_span[cd] 并遭受了一次过多的电击。\n\n在第二个测试用例中，前两次电击后我们可以确定选定字母是 #cf_span[e] 或 #cf_span[o]。Valentin 尝试了一些由这些字母组成的单词，第二次单词后可以确定选定字母是 #cf_span[e]，但 Valentin 在做出正确猜测前又进行了 3 次动作。\n\n在第三个例子中，选定字母只有在 Valentin 猜测时才能被唯一确定，因此他没有遭受任何过多的电击。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of actions.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of actions, where each $ a_i $ is one of:  \n- A word $ w_i $ (Valentin speaks),  \n- A guess $ g_i $ (Valentin guesses a letter).  \n\nLet $ \\Sigma = \\{a, b, \\dots, z\\} $ be the set of 26 lowercase English letters.  \nLet $ L \\in \\Sigma $ be the unknown selected letter.  \n\nLet $ S \\subseteq \\Sigma $ be the set of possible candidates for $ L $, initialized as $ S = \\Sigma $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. Total length of all words $ \\le 10^5 $  \n3. The last action $ a_n $ is a correct guess: $ a_n = g_n $ and $ g_n = L $  \n4. All prior guesses $ g_i $ ($ i < n $) are incorrect: $ g_i \\ne L $  \n5. For each word $ w_i $:  \n   - If Valentin receives a shock, then $ w_i \\cap L \\ne \\emptyset $ (i.e., $ L \\in \\text{chars}(w_i) $)  \n   - If no shock, then $ w_i \\cap L = \\emptyset $ (i.e., $ L \\notin \\text{chars}(w_i) $)  \n6. For each guess $ g_i $:  \n   - If shock, then $ g_i \\ne L $  \n   - If no shock, then $ g_i = L $ (only occurs at $ i = n $)  \n\n**Objective**  \nCompute the number of **excessive electric shocks**, defined as:  \n> The number of shocks received **after** the moment $ S $ becomes a singleton (i.e., $ |S| = 1 $), but before the final correct guess.  \n\nThat is:  \nLet $ t^* = \\min \\{ t \\in \\{1, \\dots, n\\} \\mid |S_t| = 1 \\} $, where $ S_t $ is the candidate set after action $ t $.  \nLet $ E $ be the set of actions $ i > t^* $ such that action $ a_i $ results in a shock.  \nThen output $ |E| $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF907C","tags":["bitmasks","implementation","strings"],"sample_group":[["5\n! abc\n. ad\n. b\n! cd\n? c","1"],["8\n! hello\n! codeforces\n? c\n. o\n? d\n? h\n. l\n? e","2"],["7\n! ababahalamaha\n? a\n? b\n? a\n? b\n? a\n? h","0"]],"created_at":"2026-03-03 11:00:39"}}