청린은 PS 실력 향상을 위해 DOJ에 가입해 지인들에게 추천받은 문제들을 풀기 시작했다.
DOJ에는 문제를 분류하기 위한 태그 시스템이 있으며, 모든 문제는 종류의 태그 중 개 이상을 가진다.
청린은 태그 목록을 길이 의 비트 문자열로 나타내기로 했다. 비트 문자열 가 나타내는 태그 목록은 의 왼쪽에서 번째 문자 가 이면 번 태그를 가지고, 이면 번 태그를 가지지 않는다. 어떤 문제가 태그 목록 를 갖는다면 가 갖는 모든 태그를 가지고, 가 갖지 않는 모든 태그를 갖지 않는다.
청린은 추천받은 문제를 바로 풀지 않고, '나중에 풀 문제' 목록에 쌓아 두었다가 한꺼번에 푸는 습관이 있다. 처음에 이 목록은 비어 있다. 여러분은 청린을 도와 다음 개의 쿼리를 처리해야 한다.
1 S x: 태그 목록 를 갖는 문제 개를 '나중에 풀 문제' 목록에 추가한다.2 S x: 태그 목록 를 갖는 문제 개를 '나중에 풀 문제' 목록에서 제거한다. 이때 '나중에 풀 문제' 목록에는 태그 목록 를 갖는 문제가 개 이상 존재함이 보장된다.3 S: 현재 '나중에 풀 문제' 목록에 존재하는 문제 중 태그 목록 가 갖는 모든 태그를 갖는 문제의 개수를 출력한다.
세 번째 쿼리에서 출력할 개수에 포함되는 문제는 에 포함된 모든 태그를 가지고 있기만 하면 된다. 즉, 인 모든 에 대해 해당 문제도 번 태그를 가지고 있어야 하며, 인 태그를 가지고 있는지는 상관없다.
청린을 도와 쿼리를 처리해보자.
Input
입력은 다음과 같은 형식으로 주어진다.
각 ()는 1 S x, 2 S x, 3 S 중 하나의 형식으로 주어진다.
Output
각 3 S 쿼리마다, 조건을 만족하는 문제의 개수를 한 줄에 하나씩 출력한다.
Constraints
- .
- .
- 각 쿼리의 는 길이가 인 비트 문자열이다.
1 S x,2 S x쿼리에서 .2 S x쿼리가 주어질 때, 현재 목록에는 태그 목록 를 갖는 문제가 개 이상 존재한다.
Subtasks
Samples
처음 두 쿼리 이후 목록에는 태그 목록 101을 갖는 문제가 개, 111을 갖는 문제가 개 있다. 따라서 3 101의 답은 이다.
그 다음 101 문제 개를 제거하면 101 문제 개와 111 문제 개가 남는다. 3 001의 답은 이다.
마지막으로 010 문제 개를 추가하면 전체 문제 수는 개이므로 3 000의 답은 이다.