Statement
\epigraph{모든 문자열에 값을 매핑하면서도 탐색을 충분히 빠르게 할 수 있을까?}{- yyyy7089}
모든 문자열을 정수에 대응하는 맵 과 빈 문자열 를 가지고 있다. 처음에 은 모든 문자열을 에 대응하고 있다.
다음 종류의 쿼리를 수행하는 프로그램을 작성하라.
1: 뒤에 문자 를 추가한다. 는 알파벳 소문자만 주어진다.2: 의 맨 뒤에서 개의 문자를 지운다. 가 빈 문자열인 경우 아무 일도 하지 않는다.3: 에 를 더한다.4: 를 출력한다.5: 뒤에 를 추가한다.
Input
첫째 줄에 쿼리의 수 가 주어진다.
둘째 줄부터 개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.
4번 쿼리는 하나 이상 주어진다.
Output
번 쿼리가 주어질 때마다 를 출력하라.
Subtasks
Samples
입력
22
3 1
1 a
3 2
1 b
3 3
1 a
3 4
4
2
4
2
4
2
4
2
4
1 a
1 b
5
4
2
4
출력
4
3
2
1
1
0
4