Problem Statement

Consider a tree in which each vertex has either a green stone or a blue stone placed on it. Among such trees, a tree is called a "Gemini Tree" if it is possible for condition 3. below to be satisfied after performing the following operations 1, 2.

1. First, perform the operation "choose a pair of vertices directly connected by an edge and swap the stones placed on them" any number of times, 0 or more.
2. Next, choose at most 1 edge and delete it.
3. At this point, the tree is split into at most 2 connected components, and in every connected component, the stones placed are of only 1 type.

The value of a "Gemini Tree" with a length defined on each edge is defined as follows.

1. First, perform the operation "choose a pair of vertices directly connected by an edge and swap the stones placed on them" any number of times. Each swap operation costs an amount equal to the length of the edge.
2. Next, choose at most 1 edge and delete it.
3. At this point, the tree is split into at most 2 connected components, and in every connected component, the stones placed are of only 1 type.
4. The minimum possible total cost of the operations in 1. when achieving 3. is the value of the "Gemini Tree".

Note that no stones are actually moved when calculating the value.

You are given a "Gemini Tree" with $N$ vertices (an odd number) with a length defined on each edge. Edge $i$ connects 2 vertices $u_i,v_i$ and its length is $w_i$. The colors of the stones placed on the vertices are represented by a string $S = s_1s_2 \dots s_N$.

You perform $Q$ operations on this tree in order. The $j$-th operation is defined by 2 integers $e_j,a_j$, and increases the length of edge $e_j$ by $a_j$. The effect of an operation persists for subsequent operations. Find the value of the tree after each operation.

Input

$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$

• All inputs are integers
• $3 \le N \le 10^5$
• $N$ is odd
• $s_i$ is either "G" or "B" and represents the color of the stone placed on vertex $i$ ("G" means green, "B" means blue)
• $1 \le u_i,v_i \le N$
• $0 \le w_i \le 10^5$
• The given graph is a "Gemini Tree"
• $1 \le Q \le 10^5$
• $1 \le e_j \le N-1$
• $1 \le a_j \le 10^5$

Output

Output $Q$ lines.
On the $j$-th line, output the value of the tree after the $j$-th operation.
Print a newline at the end of each line.

Sample

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