問題文

各頂点に、緑の石・青い石の内のどちらかが置かれているような木を考えます。このような木の内で、以下1,2の操作を行った時、3.の条件を満たす可能性がある木を「Gemini Tree」と呼びます。

1. まず、「辺で直接結ばれている頂点対を選び、それぞれに置かれている石を交換する操作」を0回以上の任意の回数行う。
2. 次に、1本以下の辺を選び削除する。
3. この時、木は最大で2つの連結成分に分かれるが、いずれの連結成分においても置かれている石の種類は1種類である。

各辺に長さの定義された「Gemini Tree」の価値を、以下のように定義します。

1. まず、「辺で直接結ばれている頂点対を選び、それぞれに置かれている石を交換する操作」を任意の回数行う。ただし、各交換操作には辺の長さと等しいコストが掛かる。
2. 次に、1本以下の辺を選び削除する。
3. この時、木は最大で2つの連結成分に分かれるが、いずれの連結成分においても置かれている石の種類は1種類である。
4. 3. を達成したとき、1.の操作のコストの総和として考えられる最小値が「Gemini Tree」の価値である。

なお、価値の算出時に実際に石を動かすことはないことに注意してください。

各辺に長さが定義された$N$頂点(奇数)の「Gemini Tree」が与えられます。辺 $i$ は2頂点 $u_i,v_i$を結び、その長さは $w_i$ です。各頂点に置かれた石の色は文字列 $S = s_1s_2 \dots s_N$ で表現されます。

この木に対し、$Q$ 回の操作を順に行います。 $j$ 回目の操作は、2つの整数 $e_j,a_j$ で定義され、辺 $e_j$ の長さを $a_j$ だけ増加させます。操作による影響は、次以降の操作時においても残ります。各操作後の木の価値を求めてください。

入力

$N$
$s_1s_2 \dots s_N$
$u_1\ v_1\ w_1$
$\vdots$
$u_{N-1}\ v_{N-1}\ w_{N-1}$
$Q$
$e_1\ a_1$
$\vdots$
$e_Q\ a_Q$

• 入力は全て整数
• $3 \le N \le 10^5$
• $N$ は奇数
• $s_i$ は "G" か "B" のどちらかで、頂点$i$に置かれた石の色を表す ("G"なら緑, "B"なら青)
• $1 \le u_i,v_i \le N$
• $0 \le w_i \le 10^5$
• 与えられるグラフは「Gemini Tree」
• $1 \le Q \le 10^5$
• $1 \le e_j \le N-1$
• $1 \le a_j \le 10^5$

出力

$Q$ 行出力してください。
$j$ 行目には、$j$ 番目の操作を行った後の木の価値を出力してください。
各行末は改行してください。

サンプル

5
GBBBB
1 2 0
1 3 0
2 4 0
2 5 0
5
1 1
2 3
3 3
4 10
2 2

0
1
1
3
4

5
BGBGB
1 2 0
1 3 0
2 4 0
2 5 1000
4
4 1
3 1
1 1
2 1

0
1
3
4

7
GGGBBBB
1 5 1
2 5 1
7 5 0
7 6 0
3 6 0
4 6 0
6
5 1
5 1
5 1
6 3
3 3
5 100000

1
2
2
3
6
11