Валентин участвует в шоу, которое называется «Шокеры». Суть проста — жюри загадало некоторую букву, неизвестную Валентину. Он должен выступить с некоторой речью, но за каждое произнесённое слово, содержащее загаданную букву, его бьют током. Он может делать предположения, какая буква загадана, однако за каждую неправильную гипотезу его также будут бить током. Шоу заканчивается, когда Валентин угадывает букву правильно.
У Валентина не идеальная память, поэтому он мог угадать букву существенно позже, чем она однозначно определялась, то есть получить несколько лишних ударов током. Лишние удары током — это те удары, которые он получил после того момента, как загаданную букву можно было однозначно определить. Вам требуется найти количество таких лишних ударов.
В первой строке находится единственное целое число n (1 ≤ n ≤ 105) — количество действий Валентина.
В следующих n строках записаны его действия, по одному в строке. Каждое действие может принадлежать одному из трёх типов:
Все сказанные слова состоят из строчных букв латинского алфавита, суммарная длина всех слов не превосходит 105.
Гарантируется, что последним действием Валентин отгадывает загаданную букву. Также гарантируется, что ранее он её не отгадывал. Помимо того гарантируется, что в каждом слове, за которое его били током, такая буква присутствует, а в словах, за которые его не били — отсутствует.
Выведите единственное целое число — количество ударов тока, которых Валентин мог избежать, если бы назвал загаданную букву сразу после того, как она однозначно определилась.
5
! abc
. ad
. b
! cd
? c
1
8
! hello
! codeforces
? c
. o
? d
? h
. l
? e
2
7
! ababahalamaha
? a
? b
? a
? b
? a
? h
0
Разберём тестовые примеры.
В первом тесте после первого слова становится понятно, что загадана одна из букв a, b, c. Из второго слова мы узнаём, что загадана не буква a. Валентин произносит слово b, и не получает удар током. В этот момент мы понимаем, что загадана буква c, однако Валентин говорит слово cd, тем самым получает один лишний удар током.
Во втором тесте после первых двух ударов мы понимаем, что загадана либо буква e, либо буква o. Валентин начинает перебирать буквы из этих двух слов, и после второй его попытки угадать букву мы понимаем, что загадана буква e. Но Валентин делает ещё 3 попытки, прежде чем добирается до этой буквы.
В третьем тесте загаданная буква однозначно определяется только когда Валентин её угадал, поэтому он не получил лишних ударов током.
Название |
---|