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.


-----Input-----

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

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.


-----Examples-----
Input
5
! abc
. ad
. b
! cd
? c

Output
1

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

Output
2

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

Output
0



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
c=set('qwertyuiopasdfghjklzxcvbnm')
ch=False
k=0
for i in range(n-1):
    s=input()
    if ch:
        if s[0]!='.':
            k+=1
    else:
        if s[0]=='.':
            c.difference_update(set(s[2:]))
        elif s[0]=='!':
            c.intersection_update(set(s[2:]))
        else:
            if s[2] in c:
                c.remove(s[2])
        if len(c)==1:
            ch=True
input()
print(k)

n = int(input())

a = [chr(i) for i in range(97, 123)]
a = set(a)
cnt = 0
f = False
for i in range(n):
    r, w = input().split()
    w = set(list(w))
    if len(a) == 1:
        f = True
    if r == ".":
        a = a - w
    elif r == "!":
        a = a & w
        cnt += int(f)
    elif r == "?" and (i+1) != n:
        a = a - w
        cnt += int(f)
    #print(a)
print(cnt)


s = "qwertyuiopasdfghjklzxcvbnm"
a = set()
for i in s:
    a.add(i)
#print(a)
n = int(input())
ans = 0
for i in range(n):
    s = input().split()
    # print(s)

    if(s[0] == "!" and len(a) == 1):
        ans+=1
    elif len(a) == 1 and s[0] == "?" and i != n-1:
        ans+=1
    elif s[0] == "?":
        try:
            a.remove(s[1])
        except Exception:
            pass
    elif s[0] == ".":
        for j in s[1]:
           # print(a)
            try:
                a.remove(j)
            except Exception:
                pass
    elif s[0] == "!":
        b = dict()
        for j in s[1]:
            b[j] = 1
        for j in a:
            try:
                b[j]+=1
            except Exception:
                pass
        a.clear()
        for j in b:
            if b[j] == 2:
                a.add(j)
    #print(a)
print(ans)

s = set()
i = 'a'
while i <= 'z':
  s.add(i)
  i = chr(ord(i)+1)
n = int(input())
c=0
for i in range(n):
  a = input().split()
  if a[0] == '.':
    s.difference_update(set(a[1]))
  elif len(s) == 1 and i != n-1:
    c+=1
  if a[0] == '!':
    s.intersection_update(set(a[1]))
  if a[0] == '?':
    if a[1] in s:
      s.remove(a[1])
print(c)


#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from string import ascii_lowercase


def main():
	n = int(input())
	can = set(ascii_lowercase)
	i = -1
	found = False
	cnt = 0
	for j in range(n):
		turn, word = input().split()
		if found and j != n - 1 and turn != '.':
			cnt += 1
		if turn == '.':
			can -= set(word)
			if len(can) == 1 and not found:
				i = j
				found = True
		elif turn == '!':
			can &= set(word) 
			if len(can) == 1 and not found:
				i = j
				found = True				
		else:
			if j == n-1:
				i = n-1
				break
			else:
				can -= set(word)
				if len(can) == 1 and not found:
					i = j
					found = True
	print(cnt)



def __starting_point():
	main()

__starting_point()

n = int(input())
nemog = set()
mog = set()
for i in range(26):
    mog.add(chr(97 + i))
    
cnt = 0
flag = False

for i in range(n):
    s = input()
    if s[0] == '.':
        for j in range(2, len(s)):
            mog.discard(s[j])
    if s[0] == '!':
        cnt += 1
        help = set()
        for j in range(2, len(s)):
            help.add(s[j])
        mog = mog & help
    if s[0] == '?':
        if i < n - 1:
            cnt += 1
            mog.discard(s[2])
        else:
            print(0)
            flag = True
    if len(mog) == 1:
        save = i
        break
if not flag:
    ans = 0
    for i in range (save + 1, n):
        s = input()
        if s[0] == '!' or (i < n - 1 and s[0] == '?'):
            ans += 1
    print(ans)

n = int(input())
y = set()
opr = False
count = 0
for i in range(97, 123):
	y.add(chr(i))
for i in range(n):
	s = input()
	s = s.split(" ")
	a = s[1]
	if not opr:
		z = set()
		for j in a:
			z.add(j)
		if s[0] == "!":
			y = y.intersection(z)
		elif s[0] == ".":
			y = y.difference(z)
		elif s[0] == "?" and i != n - 1:
			q = set()
			q.add(s[1])
			y = y.difference(q)
		if len(y) == 1:
			opr = True
	else:
		if (s[0] == "?" and i != n - 1) or s[0] == "!":
			count += 1
print(count)			

			
		
		


n = int(input())
mn = set('qwertyuiopasdfghjklzxcvbnm')
f = False
k = 0
for i in range(n):
        
    s = input().split()
    if f:
        if s[0] == '?' and set(s[1]) != mn or s[0] =='!':
            k += 1
        continue
    if s[0] == '?'and i != n-1:
        mn -= set(s[1])
    elif s[0] == '!':
        mn &= set(s[1])
    elif s[0] == '.':
        mn -= set(s[1])
    if len(mn) == 1:
        f = True
print(k)


n = int(input())
s = set("abcdefghijklmnopqrstuvwxyz")
mark = False
cnt = 0
for i in range(n):
    if len(s) == 1:
        mark = True
    tmp = input().split()
    if tmp[0] == "!":
        if mark:
            cnt += 1
        curs = set(tmp[1])
        s = s & curs
    if tmp[0] == ".":
        curs = set(tmp[1])
        s -= curs
    if tmp[0] == "?":
        if mark:
            cnt += 1
            if i == n - 1:
                cnt -= 1
        s -= set(tmp[1])
print(cnt)


n = int(input())

s = set()
for i in range(ord('a'), ord('z') + 1):
    s.add(chr(i))

k = 0
fl = False
for i in range(n - 1):
    q = input().split()
    if fl:
        if q[0] == '!' or q[0] == '?':
            k += 1
    if q[0] == '.':
        for ch in q[1]:
            s.discard(ch)
    elif q[0] == '!':
        s = s.intersection(set(q[1]))
    elif q[0] == '?':
        s.discard(q[1])
    if len(s) == 1:
        fl = True
q = input()

print(k)


q=int(input())
d=set([chr(i) for i in range(97,123)])
gf=0
for i in range(0,q-1):
    s=input()
    s1=s[2:]
    if s[0]=='!':
        if len(d)==1:
            gf+=1
        d&=set(s1)
    elif s[0]=='.':
        d=d.difference(set(s1))
    else:
        if len(d)==1:
            gf+=1
        d=d.difference(set(s1))
    
    #print(d)
s=input()
print(gf)


n=int(input())
alf='abcdefghijklmnopqrstuvwxyz'
so='';
j=n
for i in range(n):
    s=input()
    j-=1
    if s[0]=='!':
        so = '';
        for e in alf:
            if s.find(e)>-1: so+=e;
        alf=so
    elif s[0]=='.':
        so = '';
        for e in alf:
            if s.find(e)==-1: so+=e;
        alf=so
    else:
        alf=alf.replace(s[2],'')
    if len(alf)==1: break
lol=0;
p=j;
for i in range(j-1):
    s = input()
    if s[0]=='!' or s[0]=='?': lol+=1
if not(p==0):s = input()
print(lol)

n = int(input())
l1 = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'h', 'w', 'y', 'x', 'z', 'v'}
for i in range(n - 1):
    l = list(input())
    if l[0] == '.':
        l = set(l[2:])
        l1 -= l
    elif l[0] == '!':
        l = set(l[2:])
        l1 &= l
    else:
        l1 -= set(l[2])
    if len(l1) == 1:
        q = 0
        for k in range(n - i - 2):
            l = list(input())
            if l[0] != '.':
                q += 1
        print(q)
        break
if len(l1) > 1:
    print(0)


n=int(input())
mn=set()
otv=set()
k=0
for i in range(ord('a'),ord('z')+1):
    otv.add(chr(i))
for i in range(n):
    s=input().split()
    if s[0]=='!':
        otv=set(s[1])&otv
    elif s[0]=='.':
        otv-=set(s[1])
    else:
        if i!=n-1:
            otv-=set(s[1])
    if len(otv)==1:
        break
for bb in range(i+1, n):
    s=input().split()
    if s[0]!='.':
        k+=1
k-=1
if k<0:
    k=0
print(k)
    


n = int(input())
a = 0
b = 0
flag = True
t = set(list('qwertyuioplkjhgfdsazxcvbnm'))
for i in range(n):
    op, w = list(map(str, input().split()))
    w = set(list(w))
    if op == '!':
        t &= w
        a += 1
        if flag:
            b += 1
    elif op == '.':
        t = t.difference(w)
    else:
        t = t.difference(w)
        if i != n - 1:
            a += 1
            if flag:
                b += 1
    if len(t) == 1:
        flag = False
print(a - b)


a=set('abcdefghijklmnopqrstuvwxyz')
n=int(input())
for i in range (n):
    e,b=input().split()
    if e=='!':
        a.intersection_update(set(b))
    elif e=='?' and (i!=(n-1)):
        a.difference_update(set(b))
    elif e=='.':
        a.difference_update(set(b))
    if len (a)==1:
        break
s=0
for j in range (i+1,n):
    e,b=input().split()
    if e=='!' or (e=='?' and j!=(n-1)):
        s+=1
print(s)


c=int(input())
ans=0
q=0
m=[[i,1]for i in 'abcdefghijklmnopqrstuvwxyz']
for i in range(c):
    suma=0
    for j in range(26):
        suma+=m[j][1]
    if suma<2:
        q=1
    x=input()
    a=set(x[2:])
    x=x[0]
    if x=='.':
        for j in range(26):
            if m[j][0]in a:
                m[j][1]=0
    elif x=='!':
        for j in range(26):
            if not(m[j][0]in a):
                m[j][1]=0
        if q:
            ans+=1
    else:
        for j in range(26):
            if m[j][0]in a:
                m[j][1]=0
        if i!=c-1 and q:
            ans+=1
print(ans)


n = int(input())
no = set()
mb = set("abcdefghijklmnopqrstuvwxyz")
ans = 0
mark = False
for i in range(n):
    flag, save = input().split()
    if(flag == "!"):
        for_add = set()
        for j in range(len(save)):
            for_add.add(save[j])
        if(len(mb) == 0):
            mb = for_add
        else:
            mb = for_add & mb
        if(mark):
            ans += 1
    elif(flag == "."):
        for j in range(len(save)):
            no.add(save[j])
    else:
        if(i != n - 1):
            no.add(save)
            if(mark):
                ans += 1
    if(len(mb - no) == 1 or len(mb) == 1):
        mark = True
        
print(ans)

n = int(input())
let = set()
for i in range(97, 123):
    let.add(chr(i))
flag = 0
ans = 0
for i in range(n - 1):
    if len(let) == 1:
        flag = 1
    t, s = map(str, input().split())
    #print(t, s)
    if t == '!':
        now = set(list(s))
        if flag == 1:
            ans += 1
        let = let.intersection(now)
        #print(now)
        #print(let)
    if t == '?':
        if flag == 1:
            ans += 1
        if s in let:
            let.remove(s)
    if t == '.':
        now = list(s)
        for elem in now:
            if elem in let:
                let.remove(elem)
print(ans)

n = int(input())
setr = set(chr(i) for i in range(ord('a'), ord('z') + 1))
setnr = set()
ans = 0
letter =''
isq = False
a = [input() for i in range(n)]
for s in a:
    if s[0] == '.':
        setnr = setnr | set(s[2:])
    elif s[0] == '!':
        if len(setr - setnr) == 1 or isq:
            ans += 1
        if len(setr) == 0:
            setr = set(s[2:])
        else:
            setr = setr & set(s[2:])
    elif s[0] == '?' and s[2] != a[-1][2]:
        if len(setr - setnr) == 1 or isq:
            ans += 1
        else:
            setnr.add(s[2])
    elif s[0] == '?' and s[2] == a[-1][2]:
        isq = True
print(ans)


n = int(input())
l=[chr(i) for i in range(97,123)]
k=0
for i in range(n):
    d,s=list(map(str, input().split()))
    if d=='!' and len(l)!=1:
        h=0
        while h<len(l):
            if not(l[h] in s):
                l.pop(h)
            else:
                h+=1
    elif d=='.' and len(l)!=1:
        h=0
        while h<len(l):
            if l[h] in s:
                l.pop(h)
            else:
                h+=1
    elif d=='?' and len(l)!=1:
        if s in l:
            l.remove(s)
    elif (d=='?' or d=='!') and i!=n-1:
        k+=1
print(k)


n = int(input())
set1 = set()
ans = 0
for i in range(97,123):
    set1.add(chr(i))
for i in range(n):
    a, b = input().split()
    if len(set1) == 1:
        if a == "?" and i != n - 1:
            ans += 1
        if a == "!":
            ans += 1
    else:
        set2 = set()
        for i in b:
            set2.add(i)
            
        if a == ".":
            set1 -= set2
        elif a == "!":
            set1 &= set2
        elif a == "?":
            set1 -= set2
print(ans)

n = int(input())
SetA = set("abcdefghijklmnopqrstuvwxyz")
flag = False
lol = 0
b = 0
for i in range(n):
    b += 1564
    if len(SetA) == 1:
        flag = True
    pit = input().split()
    if pit[0] == "!":
        if flag:
            lol += 1
        curs = set(pit[1])
        SetA = SetA & curs
    if pit[0] == ".":
        curs = set(pit[1])
        SetA -= curs
    if pit[0] == "?":
        if flag:
            lol += 1
            if i == n - 1:
                lol -= 1
        SetA -= set(pit[1])
    b -= 1564
print(lol)

n = int(input())
a = set(list('qwertyuiopasdfghjklzxcvbnm'))
al = 0
q = 0
z = 0
for i in range(n):
    k = input().split()
    if k[0] == '.':
        a -= set(list(k[1]))
    elif k[0] == '?':
        a -= set(list(k[1]))
        al += 1
        z += 1
    else:
        a &= set(list(k[1]))
        al += 1
        z += 1
    #print(al, a)
    if len(a) == 1:
        q = i + 1
        break

if len(a) != 1:
    print(0)   


else:
    for i in range(q, n):
        k = input().split()
        if k[0] != '.':
            al += 1 
    #print(al, z)
    print(al - z - 1)


n = int(input())
poss = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}
strikes = 0
found = False
for i in range(n - 1):
    a = input().split()
    if a[0] == '!':
        poss = poss.intersection(set(a[1]))
        if found:
            strikes += 1
    elif a[0] == '.':
        poss = poss.difference(set(a[1]))
    else:
        poss = poss.difference(set(a[1]))
        if found:
            strikes += 1
    if len(poss) == 1:
        found = True
print(strikes)