#P1870H. Standard Graph Problem

Standard Graph Problem

Description

You are given a weighted directed graph with nn vertices and mm edges. Each vertex in the graph can be either highlighted or normal. Initially, all vertices are normal. The cost of the graph is defined as the minimum sum of edge weights that need to be selected so that from each normal vertex one can reach at least one highlighted vertex using the selected edges only. If it is not possible to select the edges, the cost is 1-1 instead.

Your task is to compute the cost of the graph after each of the qq queries. The queries can be of two types:

  • +  vi+\;v_i makes vertex viv_i highlighted; it is guaranteed that the vertex is normal before the query.
  •   vi-\;v_i makes vertex viv_i normal; it is guaranteed that the vertex is highlighted before the query.

Output the cost of the graph after each of the qq queries.

The first line contains three integers nn, mm, and qq (3n2105,1m,q21053 \le n \le 2 \cdot 10^5, 1 \le m, q \le 2 \cdot 10^5) — the number of vertices in the graph, the number of edges, and the number of queries.

The next mm lines contain the edges of the graph, one edge per line. The ii-th line contains three integers uiu_i, viv_i, and cic_i (1ui,vin,uivi,1ci1061 \leq u_i, v_i \leq n, u_i \ne v_i, 1 \leq c_i \leq 10^6) — the endpoints of the ii-th edge (from uiu_i to viv_i) and its weight (cic_i).

The next qq lines contain the queries, one query per line. The ii-th line contains +  vi+\;v_i, if it is a query of the first type, and   vi-\;v_i, if it is a query of the second type (1vin1 \leq v_i \leq n).

Output qq numbers. The ii-th number is the cost of the graph after the first ii queries.

Input

The first line contains three integers nn, mm, and qq (3n2105,1m,q21053 \le n \le 2 \cdot 10^5, 1 \le m, q \le 2 \cdot 10^5) — the number of vertices in the graph, the number of edges, and the number of queries.

The next mm lines contain the edges of the graph, one edge per line. The ii-th line contains three integers uiu_i, viv_i, and cic_i (1ui,vin,uivi,1ci1061 \leq u_i, v_i \leq n, u_i \ne v_i, 1 \leq c_i \leq 10^6) — the endpoints of the ii-th edge (from uiu_i to viv_i) and its weight (cic_i).

The next qq lines contain the queries, one query per line. The ii-th line contains +  vi+\;v_i, if it is a query of the first type, and   vi-\;v_i, if it is a query of the second type (1vin1 \leq v_i \leq n).

Output

Output qq numbers. The ii-th number is the cost of the graph after the first ii queries.

样例输入 1

4 5 6
1 2 1
2 3 5
3 2 3
4 1 8
2 1 4
+ 1
- 1
+ 3
+ 1
+ 4
+ 2

样例输出 1

15
-1
14
12
4
0

样例输入 2

10 14 10
8 6 4
2 5 1
3 5 4
1 6 3
1 3 7
7 2 1
6 1 3
4 10 1
4 6 5
5 4 1
5 8 10
10 9 1
9 5 1
9 7 6
+ 7
+ 8
- 7
+ 10
+ 2
- 10
+ 5
- 2
- 5
+ 3

样例输出 2

28
24
29
19
18
24
18
19
29
20

Note

In the first test:

  • After the first query, it is most profitable to select the edges with numbers 3,4,53, 4, 5, their total cost is 1515.
  • After the second query, there are no highlighted vertices, which means that there are no suitable sets of edges, the cost of the graph is 1-1.
  • After the third query, it is most profitable to select the edges with numbers 1,2,51, 2, 5, their total cost is 1414.
  • After the fourth query, it is most profitable to select the edges with numbers 44 and 55, their total cost is 1212.
  • After the fifth query, it is most profitable to select only edge number 55, its cost is 44.
  • After the sixth query, all vertices are highlighted and there is no need to select any edges, the cost of the graph is 00.