스택 복사 게임

미르코가 스택을 가지고 놀고 있다. 게임을 시작할 때 미르코에게는 번호가 $0$인 빈 스택 하나만 있다. 게임의 $i$번째 단계에서 미르코는 이미 만들어진 스택 하나를 골라 그 번호를 $v$라 하고, 그 스택을 복사한 뒤 아래 세 가지 중 하나를 수행한다.

1. 복사한 스택의 맨 위에 수 $i$를 넣는다.
2. 복사한 스택의 맨 위에 있는 수를 뺀다.
3. 스택 하나를 더 골라 그 번호를 $w$라 하고, 복사한 스택과 $w$번 스택에 함께 들어 있는 서로 다른 수가 몇 개인지 센다.

새로 만든 스택의 번호는 $i$가 된다.

미르코는 스택을 직접 다루기 싫어하므로, 이 과정을 대신 처리하는 프로그램을 작성하자. b 연산마다 스택에서 뺀 수를 출력하고, c 연산마다 조건을 만족하는 수의 개수를 출력한다.

첫 줄에 미르코의 게임 단계 수 $N$이 주어진다. ($1 \le N \le 300\,000$)

게임의 각 단계는 시간 순서대로 $1$부터 $N$까지의 번호로 구분한다.

다음 $N$개의 줄 중 $i$번째 줄에는 $i$번째 단계의 내용이 아래 세 가지 형태 중 하나로 주어진다.

• a 연산은 "a v"
• b 연산은 "b v"
• c 연산은 "c v w"

줄의 첫 글자는 연산의 종류를 나타내고, 그 뒤에 오는 한 개 또는 두 개의 수는 연산에 쓰이는 스택 번호이며 항상 $[0, i-1]$ 구간의 정수이다.

b 연산에서 수를 빼는 스택은 비어 있지 않다.

b 연산과 c 연산마다 구한 수를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

첫 번째 예제를 살펴보자. 처음에는 스택이 $S_0 = \{\}$ 하나뿐이다. 1번째 단계에서 $S_0$을 복사하고 맨 위에 $1$을 넣어 $S_1 = \{1\}$이 된다. 2번째 단계에서 $S_1$을 복사하고 맨 위에 $2$를 넣어 $S_2 = \{1, 2\}$가 된다. 3번째 단계에서 $S_2$를 복사하고 $2$를 빼서 $S_3 = \{1\}$이 된다. 4번째 단계에서 $S_2$를 복사해 $S_4$라 하고, $S_4$와 $S_3$에 함께 들어 있는 수를 세면 $1$뿐이므로 답은 $1$이다. 5번째 단계에서 $S_4$를 복사하고 $2$를 빼서 $S_5 = \{1\}$이 된다.