You are given an array of length . You are also given queries on the array and you have to process them. Queries are of two types:
: Set .
. The graph is complete, meaning every node is connected to every other node by an edge. The weight of the edge between two nodes is the maximum of their values. Formally, the edge between nodes is , where . You have to print the cost of the minimum spanning tree (MST) of this graph.
Here is an example of an unweighted complete graph with nodes (note that in our case the edges will have weights).
A spanning tree of a graph is a subset of edges taken from the graph such that they form a tree and every vertex on the graph is reachable from every other vertex via the chosen set of edges. The cost of a spanning tree is just the sum of edge weights in it. A minimum spanning tree of a graph is a spanning tree with the minimum cost.
The first line contains the integer , the number of test cases. For each test case:
The first line contains the integers
The second line contains integers describing the contents of the array
The next lines are the queries you have to process in one of the following forms:
: These integers satisfy and . In this case, you have to set .
: These integers satisfy . In this case, you have to print the cost of the MST in the graph described above.
The sum of over all test cases does not exceed
. The sum of over all test cases does not exceed
For each query of the second type, output a single number in one line - the cost of the MST of the graph constructed.
Don’t print an extra newline after each test case. Every case has at least one query of the second type.
1 5 6 1 2 3 4 5 1 1 9 1 2 8 1 3 3 1 4 3 1 5 11 2 2 5
There can be multiple ways to construct an MST.