Treeland 地铁系统由 $N$ 个车站和 $N-1$ 条双向隧道组成。这些隧道使得任意两个车站之间都可以互相到达。该系统被认为是国内最高效的：系统中任意两个车站之间都有列车通行。

来自地铁改善部门的 Alejandro 的任务是让系统变得更好，对乘客和企业更具吸引力。为此，部门收集了 $P$ 个来自公司的提案。每个提案要么是赞助某个车站（基本上是在车站上添加一个带有公司名称的标志），要么是在某个车站开设业务（如餐厅、商店等）。注意，每个车站可以接受的提案数量没有限制。

然而，有意在系统中开展业务的公司表示，除非其业务所在的车站 $X$ 是一个赞助车站，或者存在一条连接两个赞助车站且经过 $X$ 的列车路径，否则他们将撤回提案。当然，Alejandro 不希望选择最终会被撤回的提案。因此，他要确保选择一组提案，使得其中没有任何提案会被撤回。他将这样的一组提案称为“有效提案集”。

下图展示了赞助车站（红色/虚线圆圈）和业务（蓝色/点线圆圈）。(a) 中的提案集是有效的，因为车站 3 的业务提案正好位于两个赞助车站 2 和 4 之间的路径上。(b) 中的提案集也是有效的，因为车站 1 的业务提案正好位于一个赞助车站上。相反，(c) 中的提案集是无效的：尽管车站 3 的业务提案位于两个赞助车站之间的路径上，但车站 5 的业务提案却不在。

(a) 有效 (b) 有效 (c) 无效

为了选择一个有效集，Alejandro 将 $P$ 个提案（每个都写在一张纸上）从 1 到 $P$ 进行了编号。现在他想选择一个连续的提案范围，使其构成一个有效集。更准确地说，他想选择两个整数 $i$ 和 $j$（$1 \le i \le j \le P$），使得提案 $i, i+1, \dots, j$ 构成一个有效集；此外，他希望这个集合尽可能大。Alejandro 不确定他将选择的范围的起始提案 $i$ 应该是哪一个。请帮助他计算对于每个从 1 到 $P$ 的 $i$，以提案 $i$ 为起始的、构成有效集的连续提案范围的最大长度。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 10^5$)，表示地铁系统中的车站数量。每个车站由 1 到 $N$ 之间的一个不同整数标识。

接下来的 $N-1$ 行，每行包含两个整数 $U$ 和 $V$ ($1 \le U, V \le N$ 且 $U \neq V$)，表示车站 $U$ 和 $V$ 之间有一条双向隧道。保证可以通过隧道从任意车站到达其他任何车站。

下一行包含一个整数 $P$ ($1 \le P \le 10^5$)，表示公司提交的提案数量。每个提案由 1 到 $P$ 之间的一个不同整数标识。

接下来的 $P$ 行，第 $i$ 行描述提案 $i$，包含一个字符 $C$ 和一个整数 $X$ ($1 \le X \le N$)。对于赞助提案，$C$ 为小写字母“s”；对于业务提案，$C$ 为小写字母“b”。在这两种情况下，$X$ 均为对应的车站。注意，每个车站可以有任意数量的任何类型的提案。

输出格式

输出 $P$ 行。第 $i$ 行必须包含一个整数，表示以提案 $i$ 为起始的、构成有效集的连续提案范围的最大长度。

样例

样例输入 1

6
2 1
1 3
3 5
5 6
4 3
8
b 1
s 2
b 6
s 3
b 4
s 5
b 3
s 4

样例输出 1

0
1
0
5
4
3
0
1

样例输入 2

7
4 2
2 1
1 3
3 6
5 2
3 7
6
s 4
b 5
b 6
s 7
b 2
s 3

样例输出 2

1
0
0
1
0
1

样例输入 3

2
1 2
5
s 1
b 1
s 1
b 1
s 1

样例输出 3

5
4
3
2
1