Background

Tom热爱学习，所以Tom有很多书架！今天Tom终于要整理自己的书架了:)

Description

Tom准备整理 $n$ 次书架！开始时，Tom有一个下标为 $0$ 的书架，在第 $i$ 次书架整理作战中，他会拿来一个下标为 $i$ 的新书架，并选择一个之前整理过的书架 $x$ ，在新书架中放入和 $x$ 完全一样的书，再进行以下 $3$ 中操作中的一种：

​ $a.$把书本 $i$ 放在书架 $i$ 的顶上

​ $b.$把书架 $i$ 最顶上的书本拿走

​ $c.$另选一个书架 $y$ ，统计有多少本书在书架 $y$ 和书架 $i$ 中同时出现

Format

Input

第一行包含一个整数$n（1\leq n\leq 300 000）$，表示Tom整理书架的次数。

接下来的$n$行，每行遵循下面三种形式之一：

$1.\ \ a\ \ x$ 操作a

$2．b\ \ x$：操作b

$3．c\ \ x\ \ y$：操作c

其中 $0≤x,y≤i-1$ ，且对于 $b$ 操作，选中的下标为 $x$ 的不为空书架。

Output

对于每一个 $b$ 操作，输出被拿走的书；对于每一个 $c$ 操作，输出统计的同时出现的书本数。

Samples

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

Limitation

对于前$30\%$的数据：$n\leq 2000$.

另有$30\%$的数据：$n\leq 100000$，没有 $c$ 操作.

对于$100\%$的数据：$n\leq 300000$.