P. T. Tigris is a student currently studying graph theory. One day, when he was studying hard, GS appeared around the corner shyly and came up with a problem:

Given a graph with n nodes and m undirected weighted edges, every node having one of two colors, namely black (denoted as 0) and white (denoted as 1), you’re to maintain q operations of either kind:

* Change x: Change the color of x^{th} node. A black node should be changed into white one and vice versa.

* Asksum A B: Find the sum of weight of those edges whose two end points are in color A and B respectively. A and B can be either 0 or 1.

P. T. Tigris doesn’t know how to solve this problem, so he turns to you for help.

Given a graph with n nodes and m undirected weighted edges, every node having one of two colors, namely black (denoted as 0) and white (denoted as 1), you’re to maintain q operations of either kind:

* Change x: Change the color of x

* Asksum A B: Find the sum of weight of those edges whose two end points are in color A and B respectively. A and B can be either 0 or 1.

P. T. Tigris doesn’t know how to solve this problem, so he turns to you for help.

There are several test cases.

For each test case, the first line contains two integers, n and m (1 ≤ n,m ≤ 10^{5}), where n is the number of nodes and m is the number of edges.

The second line consists of 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, indicating there is an edge of weight w (1 ≤ w ≤ 2^{31} - 1) between u and v (u != v).

The next line contains only one integer q (1 ≤ q ≤ 10^{5}), the number of operations.

Each of the following q lines describes an operation mentioned before.

Input is terminated by EOF.

For each test case, the first line contains two integers, n and m (1 ≤ n,m ≤ 10

The second line consists of n integers, the i

The following m lines represent edges. Each line has three integer u, v and w, indicating there is an edge of weight w (1 ≤ w ≤ 2

The next line contains only one integer q (1 ≤ q ≤ 10

Each of the following q lines describes an operation mentioned before.

Input is terminated by EOF.

For each test case, output several lines.

The first line contains “Case X:”, where X is the test case number (starting from 1).

And then, for each “Asksum” query, output one line containing the desired answer.

The first line contains “Case X:”, where X is the test case number (starting from 1).

And then, for each “Asksum” query, output one line containing the desired answer.

提交代码