St. Petersburg is located on ~n~ islands that are connected by ~m~ bridges. Islands are labeled by integers from ~1~ to ~n~, and bridges — from ~1~ to ~m~. Every bridge connects two distinct islands. Some bridges were built in Peter the Great era, and some of them were built recently. That's why different bridges have different weight limits. Namely, only the cars with weight not exceeding ~d_i~ can drive through the ~i~-th bridge. Sometimes some of the bridges in St. Petersburg are being renovated, but this doesn't necessarily make the bridge stronger, so, some of ~d_i~ may either increase or decrease. You develop a product that will help citizens and city guests. Currently, you develop a module that has to answer two types of queries:

1. The weight limit of bridge ~b_j~ became equal to ~r_j~.
2. Count the number of islands, that can be reached by the car of weight equal to ~w_j~ from island ~s_j~.

Answer all queries of the second type.

Input

The first line contains two integers ~n~ and ~m~ — the number of islands and bridges in St. Petersburg ~(1 \le n \le 50\,000, 0 \le m \le 100\,000)~.

The ~i~-th of the following ~m~ lines contains three integers ~u_i~, ~v_i~, and ~d_i~ that describe the bridge connecting islands ~u_i~ and ~v_i~, initially its weight limit equals to ~d_i~ ~(1 \le u_i, v_i \le n; u_i \ne v_i; 1 \le d_i \le 10^9)~.

The following line contains a single integer ~q~ — the number of queries ~(1 \le q \le 100\,000)~. The following ~q~ lines contain queries.

The description of each query starts with an integer ~t_j~ ~(t_j \in \{1, 2\})~.

If ~t_j = 1~, the query is of the first type, then two integers ~b_j~ and ~r_j~ follow, they mean that the weight limit of the bridge ~b_j~ becomes equal to ~r_j~ ~(1 \le b_j \le m, 1 \le r_j \le 10^9)~.

If ~t_j = 2~, the query is of the second type, then two integers ~s_j~ and ~w_j~ follow, that describe a car of weight ~w_j~ located on island ~s_j~ ~(1 \le s_j \le n, 1 \le w_j \le 10^9)~.

Output

For each query of the second type print the answer on a separate line.

Scoring

Subtask 1 (points: 13)

~n \le 1\,000, m \le 1\,000, q \le 10\,000~.

Subtask 2 (points: 16)

Islands and bridges form a chain, ~m = n-1, u_i = i, v_i = i+1~ ~(1 \le i \le m)~.

Subtask 3 (points: 17)

Islands and bridges form a complete binary tree, ~n = 2^k-1, m = n-1, u_i = \left\lfloor \frac{i+1}{2} \right\rfloor, v_i = i+1~ ~(1 \le k \le 15, 1 \le i \le m)~.

Subtask 4 (points: 14)

All ~t_j~ equal to ~2~.

Subtask 5 (points: 13)

Islands and bridges form a tree, ~m = n-1~.

Subtask 6 (points: 27)

No additional constraint.

Sample Input 1

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

Sample Output 1

3
2
3

Sample Input 2

7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3

Sample Output 2

1
7
7
5
7
7
4

Explanation

Green lines represent bridges that the car from the query can drive through. Green vertices represent islands that are reachable by this car. Arrow points to the island, where the car is located initially.