Farmer John 注意到，如果奶牛们挤得太近，它们往往会发生争执，因此他想开设一系列新的牛棚来帮助分散它们。

每当 FJ 建造一个新牛棚时，他最多会将其与一个现有的牛棚通过双向路径连接起来。为了确保他的奶牛们分布得足够开，他有时想要确定从某个特定牛棚到从该牛棚可达的最远牛棚的距离（两个牛棚之间的距离是从一个牛棚到另一个牛棚所需经过的路径数量）。

FJ 总共会给出 $Q$ ($1 \leq Q \leq 10^5$) 个查询，每个查询的形式要么是“建造（build）”，要么是“距离（distance）”。对于建造查询，FJ 建造一个牛棚并将其与至多一个之前建造的牛棚相连。对于距离查询，FJ 要求你计算从某个特定牛棚出发，通过一系列路径可达的最远牛棚的距离。保证被查询的牛棚已经建造完成。请帮助 FJ 回答所有这些查询。

输入格式

第一行包含整数 $Q$。接下来的 $Q$ 行中，每一行包含一个查询。每个查询的形式为 "B p" 或 "Q k"，分别表示建造一个牛棚并将其与牛棚 $p$ 相连，或者询问从牛棚 $k$ 出发的最远距离（定义如上）。如果 $p = -1$，则新牛棚将不与任何其他牛棚相连。否则，$p$ 是一个已经建造完成的牛棚的编号。牛棚编号从 $1$ 开始，因此第一个建造的牛棚是 $1$ 号，第二个是 $2$ 号，依此类推。

输出格式

请为每个距离查询输出一行结果。注意，如果一个牛棚没有连接到任何其他牛棚，则其最远距离为 $0$。

样例

输入 1

7
B -1
Q 1
B 1
B 2
Q 3
B 2
Q 2

输出 1

0
2
1

说明 1

样例输入对应的牛棚网络如下：

  (1) 
    \   
     (2)---(4)
    /
  (3)

在查询 1 中，我们建造了 1 号牛棚。在查询 2 中，我们询问 1 号牛棚到其可达的最远牛棚的距离。由于 1 号牛棚没有连接到任何其他牛棚，答案为 0。在查询 3 中，我们建造了 2 号牛棚并将其连接到 1 号牛棚。在查询 4 中，我们建造了 3 号牛棚并将其连接到 2 号牛棚。在查询 5 中，我们询问 3 号牛棚到其可达的最远牛棚的距离。在这种情况下，最远的牛棚是 1 号，距离为 2。在查询 6 中，我们建造了 4 号牛棚并将其连接到 2 号牛棚。在查询 7 中，我们询问 2 号牛棚到其可达的最远牛棚的距离。1 号、3 号和 4 号牛棚距离 2 号牛棚的距离均为 1，因此这就是我们的答案。

题目来源：Anson Hu