Welcome to ZOJ
129 - ZOJ Monthly, December 2013 - F
Bellywhite's Algorithm Homework

Time Limit: 5 Seconds      Memory Limit: 65536 KB

Now, Bellywhite is doing his algorithm course homework. Here is the homework problem:

Given a graph with N vertices (numbered from 1 to N) and M undirected weighted edges, you should finish Q operations. Each operation is one of following two types:

  1. Q X: Query the weight sum of edges that meet the condition, where X is a character in {'+', '-', 'A'}.
    • If X is '+', output the weight sum of edges with positive weight.
    • If X is '-', output the weight sum of edges with negative weight.
    • If X is 'A', output the weight sum of all edges.
  2. C X: Change the weight's sign of all edges that one of its endpoint is the vertex numbered X. Changing a number's sign means changing the number into its opposite number, for example, -5 will be changed into 5 and vice versa.

Bellywhite is trapped in it nearly a week, so he turn to you, the cleverest one on earth!


There are multiple cases. There is an empty line between two cases. The first line of each case consists of three integers N, M, Q (1 ≤ N ≤ 50000, 0 ≤ M ≤ 50000, 0 ≤ Q ≤ 50000), as described above. There are M lines followed. Each line consists of three integers a, b, c (1 ≤ a, bN, ab, -50000 ≤ c ≤ 50000), which mean there is an edge between vertex a and b, weighted c (there might be multiple edges between two vertices). Then, there are Q lines followed. Each line is either operation form described above. See samples for details.


For each case, output an integer for each query operation (Type 1) meaning the sum of edges weights queried, in one line. Please output an empty line between two cases.

Sample Input

4 6 5
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
C 1
Q +
C 3
Q -

2 1 3
1 2 -3
C 1
Q -

Sample Output



Author: YU, Xiaoyao
Submit    Status