全球化最终还是影响到了 Byteotia，邮递员 Byteasar 也不例外。他曾经漫步在宁静村庄间的乡间小道上，而如今却在高速公路上飞驰。但他对往昔岁月的漫步依然怀有温柔的眷恋。

在过去，Byteotia 的 $n$ 个村庄（编号从 $1$ 到 $n$）由双向土路连接，使得人们从任何其他村庄出发，都只有唯一的一条路径可以到达 $1$ 号村庄（称为 Bitburg）。这条唯一的路径仅经过编号小于或等于起始村庄编号的村庄。此外，每条道路连接两个不同的村庄，且不经过任何其他村庄。道路在村庄之外不会相交，但隧道和高架桥也是存在的。

随着时间的推移，道路被陆续改建为高速公路。Byteasar 清楚地记得每条乡间土路消失的时间。如今，Byteotia 已经没有乡间小道了——它们全部被改建成了高速公路，将村庄连接成了 Byteotia 大都市。

Byteasar 回忆起他给这些村庄送信的旅程。每次他都从 Bitburg 出发，目的地是某个特定的村庄。他请求你计算，对于每一次旅程（发生在特定的时间点，从 Bitburg 到达指定的村庄），他经过了多少条乡间土路。

编写一个程序，完成以下任务：

• 从标准输入读取：
  • 曾经连接 Byteotia 村庄的道路描述；
  • 事件序列：Byteasar 的旅程以及各条道路被改建为高速公路的时间点；
  • 对于每一次旅程，计算 Byteasar 必须经过的乡间土路数量；
• 将结果写入标准输出。

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 250\,000$)，表示 Byteotia 的村庄数量。接下来的 $n-1$ 行包含道路描述，每行包含两个整数 $a, b$ ($1 \le a < b \le n$)，由空格分隔，表示连接这两个村庄的道路。下一行包含一个整数 $m$ ($1 \le m \le 250\,000$)，表示 Byteasar 进行的旅程次数。接下来的 $n+m-1$ 行按时间顺序包含事件描述：

• 格式为 “A $a$ $b$”（其中 $a < b$）的描述表示连接村庄 $a$ 和 $b$ 的乡间土路在此时刻被改建为高速公路。
• 格式为 “W $a$” 的描述表示 Byteasar 从 Bitburg 到达村庄 $a$ 的旅程。

输出格式

程序应向标准输出写入恰好 $m$ 个整数，每行一个，表示 Byteasar 在其各次旅程中经过的乡间土路数量。

样例

输入 1

5
1 2
1 3
1 4
4 5
4
W 5
A 1 4
W 5
A 4 5
W 5
W 2
A 1 2
A 1 3

输出 1

2
1
0
1