Given an undirected graph with n nodes and m weighted edges, every node having one of two colors - black (denoted as 0) and white (denoted as 1). You are to perform q operations of two kinds:

1. C x: Change the x-th node´s color. A black node should be changed into a white node, and vice versa.
2. Q A B: Find the sum of weight of edges whose two end points of color A and B. A and B can be either 0 or 1.

Input

The first line contains two integers n (1 ≤ n ≤ 10⁵) and m (1 ≤ m ≤ 10⁵) specified above.

The second line contains n integers, the i-th of which represents the color of the i-th node, 0 for black and 1 for white.

The following m lines represent edges. Each line has three integer u, v and w (1 ≤ u, v ≤ n, u ≠ v), indicating there is an edge of weight w between u and v. w fits into 32-bit signed integer.

The next line contains only one integer q (1 ≤ q ≤ 10⁵), the number of operations.

The following q lines - operations mentioned above. See samples for detailed format.

Output

For each Q query, print one line containing the desired answer. See samples for detailed format.

Example

Input:
4 3
0 0 0 0
1 2 1
2 3 2
3 4 3
4
Q 0 0
C 2
Q 0 0
Q 0 1
Output:
6
3
3

Input:
4 3
0 1 0 0
1 2 1
2 3 2
3 4 3
4
Q 0 0
C 3
Q 0 0
Q 0 1

Output:
3
0
4

This problem has a somewhat strict source limit and time limit.