단어 암기

면접 대비

시간 제한4초메모리 제한1024 MB

요약

현재 기억하고 있는 알파벳을 관리하면서, 알파벳을 잊거나 떠올리는 질의마다 기억한 글자만으로 이루어진 단어의 개수를 센다.

문제

준석이는 영어 단어를 외우려고 한다. 사전에는 N개의 단어가 적혀 있다. 모든 단어는 소문자로 되어 있다. 단어에 들어 있는 모든 알파벳을 알고 있을 때 그 단어를 완전히 안다고 한다.

다음과 같은 쿼리가 주어진다.

처음에는 모든 알파벳을 기억하고 있고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다.

각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라.

첫 번째 줄에는 정수 N (1 ≤ N ≤ 10⁴)과 M (1 ≤ M ≤ 5×10⁴)이 주어진다.

다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 10³을 넘지 않는다.

다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다. o는 1, 2 중 하나이고, x는 알파벳 소문자이다.

o가 1이면 x를 잊는다는 뜻이고, o가 2면 x를 기억해 낸다는 뜻이다. o가 1일 때는 x를 기억하고 있었음이 보장되고, o가 2일 때는 x를 잊고 있었음이 보장된다.

각 쿼리마다 정수 하나를 출력한다.

예제 1

입력

5 10
apple
actual
banana
brick
courts
1 l
1 b
1 c
1 n
2 l
2 b
1 s
2 c
2 s
2 n

예상 출력