GRAPH2 - Graph


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^5) and m (1 <= m <= 10^5) 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^5), 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.


hide comments
[Rampage] Blue.Mary: 2016-09-28 03:44:38

Q(0,1) = Q(1,0).

johbuntu: 2016-09-27 23:43:59

Is Q(0, 1) = Q(1, 0) ?


Added by:Fudan University Problem Setters
Date:2012-11-21
Time limit:1s
Source limit:2048B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:ACM/ICPC Regional Contest, Chengdu 2012