Problem statement

You are given a connected undirected graph $G=(V,E)$ with:

• $|V| = n$ vertices $(1 \leq n \leq 5 \times 10^4)$.
• $|E| = m$ edges $(n - 1 \leq m \leq n)$.
• Each edge $e_i=(u_i,v_i)$ having weight $w_i$.

Initially, each vertex $u$ has a color $\text{color}_u$ $(1 \leq \text{color}_u \leq n)$.

You must process $Q$ queries of the following two types:

• $1$ $u$ $c$: Change the color of vertex $u$ to $c$ $(1 \leq c \leq n)$.
• $2$ $k$: Let $S_k = \{v \in V \mid \text{color}_v \leq k \}$. Find the minimum total weight of edges needed to build a connected subgraph that contains all vertices in $S_k$. You may include any vertices with color $> k$ if needed to connect the vertices in $S_k$. If $S_k$ has at most one vertex, the cost is $0$.

For each query of type $2$, output the computed minimum total weight.

Input

• The first line contains two integers $n$ and $m$ - The number of vertices and the number of edges.
• The next line contains $n$ integers $\text{color}_1, \text{color}_2, \dots, \text{color}_n$ denote the initial colors of the vertices.
• The next $m$ lines, each contain three integers $u_i$, $v_i$, $w_i$ - an edge between two vertices $u_i$ and $v_i$ with weight $w_i$ $(1 \leq u_i, v_i \leq n, u_i \neq v_i)$.
• The next line contains an integers $Q$ - The number of queries.
• The next $Q$ lines, each describe a query in one of the following formats:
  • $1$ $u$ $c$: Change the color of vertex $u$ to $c$.
  • $2$ $k$: Find the minimum connection cost for threshold $k$.

Output

For each query type $2$ $k$, output a single integer - the minimum total edge weight required to connect all vertices with color $\leq k$.

Sample Input 1

5 4
1 3 5 2 4
1 2 2
2 3 3
3 4 4
4 5 5
7
2 3
1 4 4
2 3
2 4
1 3 3
1 5 6
2 5

Sample Output 1

9
2
14
9

Sample Input 2

5 5
1 3 2 4 5
1 2 1
2 3 2
3 1 3
2 4 4
3 5 5
5
2 2
2 3
1 4 2
2 2
2 5

Sample Output 2

3
3
7
12

Constraints

• $1 \leq n, Q \leq 5 \times 10^4$.
• $n - 1 \leq m \leq n$.
• $1 \leq \text{color}_i, c, k \leq n$.
• $1 \leq w_i \leq 10^9$.
• The input graph is connected.

Subtasks

• Subtask 1 (5 points): $n, Q \leq 2000$, $m = n - 1$.
• Subtask 2 (5 points): $n, Q \leq 2000$, $m = n$.
• Subtask 3 (10 points): $\max\{\text{color}_i, c, k\} \leq 200$, $m = n - 1$.
• Subtask 4 (10 points): $\max\{\text{color}_i, c, k\} \leq 200$, $m = n$.
• Subtask 5 (20 points): $m = n - 1$.
• Subtask 6 (20 points): $m = n$.
• Subtask 7 (30 points): No additional constraints.