Background

In youyou's class, height may be a sensitive topic.

Problem Description

There are $n$ students in youyou's class and $m$ pairs of friends. For the $i$-th friend relationship, there is a sensitivity value $k_i$ related to height, and the sensitivity value may change.

We define that if two students are friends, then there must exist some relationship that directly connects these two students.

We define that if two students are close friends, then there must exist a direct or indirect relationship that connects these two students.

For example, if there are relationships $(1,2)$ and $(2,3)$, then $1$ and $2$ are friends, but $1$ and $3$ are close friends.

Now, military training is about to begin. Students need to collect their training uniforms. If a student receives a uniform of size $p$, then all students will break friendships with those friends whose relationship sensitivity value is less than $p$. That is, for every friend relationship, if its sensitivity value is less than $p$, then this friend relationship will be disconnected. However, when the next student receives a uniform, all friendships that were disconnected previously will be restored.

Since collecting uniforms is a complicated process and youyou is very interested in it, there are $q$ operations in total, and there are three types of operations:

• Operation $1$, in the form 1 x, means a student receives a uniform of size $x$.

• Operation $2$, in the form 2 x, asks how many close friends student $x$ still has (including themself).

• Operation $3$, in the form 3 x y, means the sensitivity value of the $x$-th friend relationship becomes $y$. In particular, the relative order of sensitivity values will not change$^*$ (see details below), and any relationships that have already been disconnected will not be restored.

Note: "close friends" and "friends" are two different concepts. Friends are always close friends, but close friends are not necessarily friends.

$^*$: "The relative order does not change" means that among all current sensitivity values, the modified sensitivity value has the same rank as the original one.

For example, if the original sensitivity values among all friend pairs are $\{1,2,3,5,6\}$, the rank of $3$ is $3$, so $3$ can only be changed to one of $3,4$ in order to keep the rank unchanged, i.e. its position in the relative order does not change.

Input Format

The first line contains three positive integers $n,m,q$.

In the next $m$ lines, $m$ friend relationships are given. For the $i$-th line, three positive integers $x_i,y_i,k_i$ are given.

In the last $q$ lines, $q$ operations are given. For each operation, a positive integer $op$ is given, indicating the operation type.

When $op=1$, one more positive integer $x$ is given, meaning a student receives a uniform of size $x$.

When $op=2$, one more positive integer $x$ is given, meaning a query.

When $op=3$, two more positive integers $x,y$ are given, meaning an update.

Output Format

For each query operation, output an integer $x$, meaning how many close friends the queried student has (including themself). It is guaranteed that for every test point, there is at least one query operation.

4 3 3
1 2 156
1 4 42
2 3 1
1 26963
3 3 40
2 4

1

7 6 7
1 2 292
1 3 274
1 4 221
1 5 156
3 4 42
3 6 40
1 30
3 4 50
2 6
3 3 250
3 1 298
1 280
2 1

6
2

Hint

Sample Explanation #1

As shown in the figure, this is the initial relationship graph.

The first operation is: a student receives a uniform of size $26963$, so all edges in the graph will be disconnected.

The next operation: the weight of the third friend pair, i.e. edge $(2,3)$, becomes $40$.

The next operation: query the number of close friends of student $4$. Since there are no existing edges, the answer is $1$.

Constraints

Let $c_i$ denote the uniform size received in operation type $1$ in a query context, and let $e_i$ denote the sensitivity value after a modification.

For $100\%$ of the data, $1 \le n,m,q,x_i,y_i \le 4 \times 10^5$, $1 \le k_i,c_i,e_i \le 1 \times 10^9$, and $m \le \min\{\frac{n(n-1)}{2},4 \times 10^5\}$.

Also, the data guarantees that at any moment, all sensitivity values among all friend relationships are pairwise distinct.

Please pay attention to the impact of constant factors on time and memory usage.

Translated by ChatGPT 5