题目描述

圣彼得堡市内所有水路长度总和约 282 千米，市内水域面积占城市面积的 7%。——来自维基百科

圣彼得堡位于由 $m$ 座桥梁连接而成的 $n$ 个岛屿上。岛屿用 $1$ 到 $n$ 的整数编号，桥梁用 $1$ 到 $m$ 的整数编号。每座桥连接两个不同的岛屿。有些桥梁是在彼得大帝时代建造的，其中一些是近期建造的。这导致了不同的桥梁可能有不同的重量限制。更具体地，只有重量不超过 $d_i$ 的汽车才能通过第 $i$ 座桥梁。有时圣彼得堡的一些桥梁会进行翻新，但这并不一定会使桥梁承重变得更好，也就是说，进行翻新的桥梁的 $d_i$ 可能会增加或减少。

你准备开发一个产品，用于帮助公民和城市客人。目前，你开发的模块要能执行两种类型的操作：

1. 将桥梁 $b_j$ 的重量限制改为 $r_j$。
2. 统计一辆重为 $w_j$ 的汽车从岛屿 $s_j$ 出发能够到达多少个不同的岛屿。

请你回答所有第二种操作的答案。

---

输入格式

第一行包含两个整数 $n$ 和 $m$——表示圣彼得堡的岛屿数量与桥梁数量。

接下来 $m$ 行，每行三个整数 $u_i, v_i, d_i$。第 $i$ 行的整数描述了一座连接岛屿 $u_i$ 和 $v_i$，初始时重量限制为 $d_i$ 的桥梁。

接下来一行一个整数 $q$——表示操作的数量。

接下来 $q$ 行按顺序每行描述一个操作。

每行第一个整数 $t_j$ 表示操作类型：

• 若 $t_j = 1$，则该操作是第一种类型，该行接下来给定两个整数 $b_j$ 和 $r_j$，表示桥梁 $b_j$ 的重量限制将变为 $r_j$。
• 若 $t_j = 2$，则该操作是第二种类型，该行接下来给定两个整数 $s_j$ 和 $w_j$，表示一辆重为 $w_j$ 的汽车将要从第 $s_j$ 个岛屿出发。

---

输出格式

对于每个第二种类型的询问，输出一行一个整数表示答案。

---

样例

样例 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

输出

3
2
3

说明

绿线表示当前询问的汽车可以通过的桥梁。绿色顶点代表这辆车可以到达的岛屿。箭头指向汽车最初所在的岛屿。

---

样例 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

输出

1
7
7
5
7
7
4

---

数据范围与提示

对于全部数据，$1 \le n \le 5 \times 10^4$，$0 \le m \le 10^5$，$1 \le q \le 10^5$。

保证 $1 \le u_i, v_i, s_j \le n$，$u_i \neq v_i$，$1 \le d_i, r_j, w_j \le 10^9$，$1 \le b_j \le m$，$t_j \in \{1, 2\}$。

详细子任务附加限制与分值如下表。

子任务	附加限制	分值
1	$n, m \le 10^3, q \le 10^4$	13
2	岛屿和桥梁将形成一个树结构，$m = n - 1$，$u_i = i$，$v_i = i + 1$ $(1 \le i \le m)$	16
3	岛屿和桥梁将形成一个完全二叉树结构，$n = 2^k - 1$，$m = n - 1$，$u_i = \lfloor \frac{i+1}{2} \rfloor$，$v_i = i + 1$ $(1 \le k \le 15, 1 \le i \le m)$	17
4	所有 $t_j$ 均为 $2$	14
5	岛屿和桥梁将形成一个树结构，$m = n - 1$	13
6	无特殊限制	27