考虑一棵带权树，每个顶点上放置着一枚金币或铜币。如果以下过程可行，则称该树为“神圣树”（Divine Tree）：

1. 重复以下操作零次或多次：选择一对直接相连的顶点，交换放置在这些顶点上的硬币。
2. 从树中删除至多一条边。此操作只能在完成所有第 1 类操作后执行一次。
3. 在执行第 2 类操作后，树被分为至多两棵树，且对于每一棵结果树，其所有顶点上的硬币金属种类相同。

第 1 类操作中，每次操作的代价等于所选边的权重。神圣树的代价定义为转换该树所需的所有第 1 类操作的最小总代价。

给定一棵有 $n$ 个顶点的树，其中 $n$ 为奇数。你可以假设给定的树是一棵神圣树。设第 $i$ 条边的权重为 $w_i$。

树的生长方式如下：发生 $q$ 次生长事件。在第 $j$ 次事件中，选择其中一条边 $e_j$，其权重增加 $d_j$。生长效果是永久性的。

你的任务是输出每次事件后神圣树的代价。

输入格式

第一行包含一个整数 $n$：给定神圣树的顶点数（$3 \le n < 10^5$；$n$ 为奇数）。

第二行包含一个长度为 $n$ 的字符串，由大写字母 G 和 B 组成。如果字符串中第 $i$ 个字母为 G，则顶点 $i$ 最初包含一枚金币；如果为 B，则包含一枚铜币。

接下来的 $n-1$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$，表示第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，权重为 $w_i$（$1 \le u_i, v_i \le n; u_i \neq v_i; 0 \le w_i \le 10^5$）。你可以假设给定的图是一棵神圣树。

随后一行包含一个整数 $q$：事件的数量（$1 \le q \le 10^5$）。

接下来的 $q$ 行，每行包含两个整数 $e_j$ 和 $d_j$：生长边的编号和权重增加量（$1 \le e_j \le n-1; 1 \le d_j \le 10^5$）。

输出格式

输出 $q$ 行。在第 $j$ 行输出第 $j$ 次事件后神圣树的代价。

样例

样例输入 1

5
BGGGG
1 3 0
2 1 0
5 2 0
2 4 0
5
2 1
1 3
4 4
3 10
1 2

样例输出 1

0
1
1
3
5

样例输入 2

5
GBBGB
3 2 0
2 1 0
1 4 0
1 5 1000
4
4 1
3 1
2 1
1 1

样例输出 2

0
1
3
4

样例输入 3

7
GGBBBBG
1 5 101
2 5 101
3 5 100
3 6 100
4 6 100
7 6 100
6
6 1
6 1
6 1
5 3
3 3
6 12345

样例输出 3

301
302
303
303
306
711