성열이는 N+1개의 스택을 만들려고 한다. 성열이는 우선 0번 스택(빈 스택)을 만든다. 그런 다음 1~N번 스택을 순서대로 만든다.

k번 스택은 v번 스택의 내용을 그대로 복사한 후 아래 세 가지 연산 중 하나를 적용해서 스택을 변형해서 만든다.

a. 스택에 k를 넣는다. (push)
b. 스택에서 원소 하나를 뺀다. (pop)
c. 다른 스택 w를 선택해서 자신과 w에 공통으로 들어있는 원소의 개수를 센다. (count)

평범한 방법으로 N개의 스택을 일일이 만들면 메모리가 부족할 수 있다. 보다 효율적으로 스택을 만드는 방법을 생각해보자.

입력 형식

• 첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 300,000)
• 두 번째 줄부터 N개의 줄에는 성열이가 스택을 만든 방법이 아래 형식에 따라 주어진다.
  • - "a v" : k번 스택을 만들 때 연산 a를 사용한다.
  • - "b v" : k번 스택을 만들 때 연산 b를 사용한다.
  • - "c v w" : k번 스택을 만들 때 연산 c를 사용한다.

출력 형식

입출력 예

입력

5
a 0
a 1
b 2
c 2 3
b 4

출력

2
1
2

입력

11
a 0
a 1
a 2
a 3
a 2
c 4 5
a 5
a 6
c 8 7
b 8
b 8

출력

2
2
8
8

입력 예 1 설명
0번 스택은 {} (빈 스택)이다.
1번 스택은 {1}이고 2번 스택은 {1, 2}이다.
3번 스택은 {1, 2}에서 2를 뺀 {1}이다.
4번 스택은 {1, 2}이며 3번 스택에도 포함한 원소는 1 뿐이다.
5번 스택은 {1, 2}에서 2를 뺀 {1}이다. 

a. place number i on top of the new stack
b. remove the number from the top of the new stack
c. choose another stack denoted with w and count how many different numbers exist that are in the new stack

Mirko doesn’t like to work with stacks so he wants you to write a programme that will do it for him. For each operation of type b output the number removed from stack and for each operation of type c count the required numbers and output how many of them there are.

입력

• The first line of input contains the integer N (1 <= N <= 300 000), the number of steps in Mirko’s game. The steps of the game are chronologically denoted with the first N integers.
• The i-th of the following N lines contains the description of the i th step of the game in one of the following three forms:
  • "a v" for operation of type a.
  • "b v" for operation of type b.
  • "c v w" for operation of type c.
  The first character in the line denotes the type of operation and the following one or two denote the accompanying stack labels that will always be integers from the interval [0, i - 1].

  For each operation of type b, the stack we’re removing the element from will not be empty.

출력

입출력 예

입력

5
a 0
a 1
b 2
c 2 3
b 4

출력

2
1
2

입력

11
a 0
a 1
a 2
a 3
a 2
c 4 5
a 5
a 6
c 8 7
b 8
b 8

출력

2
2
8
8

Clarification of the first example: In the beginning, we have the stack S0 = {}. In the first step, we copy S0 and place
number 1 on top, so S1 = {1}. In the second step, we copy S1 and place 2 on top of it, S2 = {1, 2}. In the third step we
copy S2 and remove number 2 from it, S3 = {1}. In the fourth step we copy S2 and denote the copy with S4, then count
the numbers appearing in the newly created stack S4 and stack S3, the only such number is number 1 so the solution is 1.
In the fifth step we copy S4 and remove number 2 from it, S5 = {1}.

출처:coci 2013/2014 5/6
번역:functionx