Limits 1s, 512 MB

You are given an array aa of length nn. You are also given qq queries on the array and you have to process them. Queries are of two types:

  • 1  i  v1~~i~~v: Set a[i]=va[i]=v.

  • 2  L  R2~~L~~R: Construct a complete graph on exactly RL+1R-L+1 nodes L,L+1,,RL,L+1,\ldots,R. 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 u,vu,v is max(a[u],a[v])\max(a[u],a[v]), where Lu<vRL\leq u<v\leq R. 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 44 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.

Input

The first line contains the integer TT (1T100000)(1 \leq T \leq 100000), the number of test cases. For each test case:

The first line contains the integers nn (1n200000)(1 \leq n \leq 200000) and qq (1q100000)(1 \leq q \leq 100000).

The second line contains nn integers describing the contents of the array aa (1a[i]2×109)(1 \leq a[i] \leq 2\times 10^9).

The next qq lines are the queries you have to process in one of the following forms:

  • 1  i  v1~~i~~v: These integers satisfy 1in1 \leq i \leq n and 1v2×1091 \leq v \leq 2\times 10^9. In this case, you have to set a[i]=va[i]=v.

  • 2  L  R2~~L~~R: These integers satisfy 1LRN1\leq L\leq R\leq N. In this case, you have to print the cost of the MST in the graph described above.

The sum of nn over all test cases does not exceed 2×1052\times 10^5. The sum of qq over all test cases does not exceed 10510^5.

Output

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.

Sample

InputOutput
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
22

There can be multiple ways to construct an MST.


Submit

Login to submit.

Statistics

88% Solution Ratio
efat1531Earliest, 6M ago
prodip_bsmrstuFastest, 0.1s
Alom_ShantoLightest, 7.0 MB
fahimcp495Shortest, 1439B
Toph uses cookies. By continuing you agree to our Cookie Policy.