Z君搬砖

题目描述

有n块砖，编号为1...n。$(1\le n\le3\cdot10^{6})$ 有两种操作。

• 1. M x y 把编号为x的砖所在的一摞砖搬到编号为y的砖所在的一摞砖的上面。如果x和y在同一摞砖则忽略这个操作。
• 2. C x 查询x下面压着多少块砖。

x,y为整数且$1\le x,y\le n$。

输入

只有一组数据。

第一行为一个整数m，表示操作的个数。$(1\le m\le10^{6})$

接下来m行表示每个操作。格式如上所述。

输出

对于每个查询操作，输出对应的答案

输入样例

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

输出样例

1
0
2

样例解释

对于这组样例显然n至少为6。

• 1. 把1搬到6的上面。

• 2. 1下面压着一块砖——6。

• 3. 把2搬到4的上面。

• 4. 把{2,4}这一摞砖搬到{1,6}上面。

• 5. 3下面为空。

• 6. 4下面压着1和6两块砖。