Shockers

题意翻译

### **题目描述** ​ Valentin 参加了一个名为 “Shockers” 的节目。节目规则非常简单:评委会选择一个 Valentin 不知道的字母。他需要做一个小演讲,但每当他说出包含选定字母的单词时,他就会受到一次电击。他可以猜测选定的字母是哪一个,但是每猜错一次他也会受到一次电击。当 Valentin 成功猜出选定的字母时,节目结束。Valentin 无法记住所有的事情,所以他可能在选定字母已经能被确定之后很久才猜出选定字母,并因此遭受多余的电击。多余的电击是指 Valentin 在选定字母可以明确被猜出之后所遭受的电击。你需要求出多余电击的次数。 ### **输入格式** 第一行包含一个单独的整数 $n (1\le n\le 10^5)$,代表 Valentin 行动的次数。 接下来 $n$ 行描述他的操作,每行描述一个操作。每个操作只可能是以下三个中的一个: 1. Valentin 说出了某个单词并且没有遭受电击。这个行动用字符串". w"(不带引号)描述,其中 "." 是一个点(ASCII 码 46),而 "w" 是 Valentin 说的单词。 2. Valentin 说出了某个单词并且遭受了电击。这个行动用字符串 "! w"(不带引号)描述,其中 "!" 是一个感叹号(ASCII 码 33),而 "w" 是 Valentin 说的单词。 3. Valentin 猜测了选定的字母。这个行动用字符串 "? s"(不带引号)描述,其中 "?" 是一个问号(ASCII 码 63),而 "s" 是 Valentin 猜测的字母——小写的英文字母。 所有的单词都只由小写的英文字母组成。所有单词的总长度不超过 $10^5$。 保证最后一个行动是关于选定字母的猜测。同时,保证在最后一个行动之前,Valentin 没有成功猜到选定字母。此外,如果 Valentin 在说出某个单词后遭受电击,那么保证这个单词包含了选定字母;反之,如果 Valentin 在发音某个单词后没有遭受电击,那么这个单词绝对不包含选定字母。 ### **输出格式** 输出一个整数——如果 Valentin 在选定字母被唯一确定后立即猜出,他本可以避免的电击次数(即多余电击的次数)。 ### **说明/提示** 在样例一中,在第一个行动之后,选定字母变得清楚,它是以下字母之一:a、b、c。在第二个行动之后,我们可以确定选定字母不是 a。Valentin 告诉了单词 "b",并没有受到电击(所以也不是 b)。在那之后,选定字母应该是 c,但是 Valentin 发音了单词 "cd" 并且受到了多余的电击。 在样例二中,在前两次电击之后,我们知道选定字母是 e 或 o。Valentin 尝试了一些由这些字母组成的单词,在第二个单词之后我们知道选定字母是 e,但是 Valentin 在做出正确的猜测之前还进行了 3 次行动。 在第三个例子中,只有当 Valentin 猜中选定字母时,才能唯一确定它,所以他没有受到多余的电击。

题目描述

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. Valentin 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.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 1<=n<=10^{5} $ ) — the number of actions Valentin did. The next $ n $ lines contain descriptions of his actions, each line contains description of one action. Each action can be of one of three types: 1. 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. 2. 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. 3. 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. All words consist only of lowercase English letters. The total length of all words does not exceed $ 10^{5} $ . It 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.

输出格式


Output 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.

输入输出样例

输入样例 #1

5
! abc
. ad
. b
! cd
? c

输出样例 #1

1

输入样例 #2

8
! hello
! codeforces
? c
. o
? d
? h
. l
? e

输出样例 #2

2

输入样例 #3

7
! ababahalamaha
? a
? b
? a
? b
? a
? h

输出样例 #3

0

说明

In 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. In 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. In the third example the selected letter can be uniquely determined only when Valentin guesses it, so he didn't get excessive electric shocks.