有 $N$ 座城市（编号从 $1$ 到 $N$），由 $M$ 条双向道路连接，使得从任意城市出发，都可以通过一条或多条道路到达其他任何城市。第 $i$ 座城市具有经济价值 $S_i$，每条道路直接连接两座不同的城市。
共有 $Q$ 个查询，需要依次执行，每个查询由一个元组 $(A_i, B_i, C_i)$ 表示：
- 如果 $A_i = 0$，你需要将城市 $B_i$ 的经济价值修改为 $C_i$。
- 如果 $A_i = 1$，你需要输出以下问题的答案：假设有两名商人，其中一人在城市 $B_i$，另一人在城市 $C_i$。他们商定一个非负整数 $X$，其中 $X$ 是他们四处走动的天数。每天，两名商人都移动到当前所在城市的任意相邻城市，他们重复此过程 $X$ 天。他们不能连续两天停留在同一个城市，但可以重新访问之前访问过的城市。$X$ 天后，他们应该位于某些城市，使得这两座城市的经济价值之差最小。输出该最小差值。注意，两名商人最终所在的城市可以是同一座城市。
输入格式
第一行包含两个整数：$N$ 和 $M$ ($1 \le N \le 100,000; 1 \le M \le 200,000$)，表示城市和道路的数量。第二行包含 $N$ 个整数：$S_1, S_2, \dots, S_N$ ($0 \le S_i \le 1,000,000,000$)，表示每座城市的经济价值。接下来的 $M$ 行，每行包含两个整数：$u_i, v_i$ ($1 \le u_i, v_i \le N; u_i \neq v_i$)，表示第 $i$ 条道路连接城市 $u_i$ 和城市 $v_i$。保证从任意城市出发，都可以通过一条或多条道路到达其他任何城市。下一行包含一个整数：$Q$ ($1 \le Q \le 100,000$)，表示查询的数量。接下来的 $Q$ 行，每行包含三个整数：$A_i, B_i, C_i$ ($0 \le A_i \le 1$)，表示查询。对于每个查询，如果 $A_i = 0$，则 $1 \le B_i \le N$ 且 $0 \le C_i \le 1,000,000,000$；否则 $1 \le B_i, C_i \le N$。保证至少有一个查询满足 $A_i = 1$。
输出格式
对于每个 $A_i = 1$ 的查询，输出商人 $X$ 天后能够到达的两座城市之间经济价值的最小差值。注意，$X$ 的值可以是任意非负整数，且在不同查询之间相互独立。
样例
样例输入 1
6 6 0 0 0 0 0 0 1 2 1 6 5 1 2 3 3 4 3 5 7 1 1 2 0 1 10 0 3 20 1 1 2 0 4 11 1 1 3 1 1 6
样例输出 1
0 10 0 1
说明
第一个样例的道路配置和查询说明如下：
- 最初所有城市的经济价值均为 $0$。
- 第 $1$ 个查询：
1 1 2。由于所有城市的经济价值相同（即 $0$），他们可以决定任意 $X$ 并移动到他们想要的任何城市；差值为 $0$。 - 第 $4$ 个查询：
1 1 2。此查询与第 $1$ 个查询相同，但现在城市 $1$ 的经济价值为 $10$（由于第 $2$ 个查询），城市 $3$ 的经济价值为 $20$（由于第 $3$ 个查询）。如果他们选择 $X = 0$，可以达到 $10$ 的最小差值。以下是一些差值不是最小的例子：- $X = 1$，第一位商人从城市 $1$ 移动到城市 $5$（经济价值为 $0$），第二位商人从城市 $2$ 移动到城市 $3$（经济价值为 $20$）。两座最终城市的经济价值之差为 $20$。
- $X = 2$，第一位商人从城市 $1$ 移动到城市 $5$，再到城市 $3$（经济价值为 $20$），第二位商人从城市 $2$ 移动到城市 $3$，再到城市 $4$（经济价值为 $0$）。两座最终城市的经济价值之差为 $20$。
- 可以通过 $X = 1$ 达到 $10$ 的最小差值，例如，第一位商人从城市 $1$ 移动到城市 $2$（经济价值为 $0$），第二位商人从城市 $2$ 移动到城市 $1$（经济价值为 $10$）。也可以通过 $X = 2$ 达到此结果，例如，第一位商人从城市 $1$ 移动到城市 $5$，再到城市 $1$（经济价值为 $10$），第二位商人从城市 $2$ 移动到城市 $3$，再到城市 $2$（经济价值为 $0$）。在所有可能的移动中，此情况下能达到的最小差值为 $10$。
- 第 $6$ 个查询：
1 1 3。两位商人可以选择 $X = 1$ 并一起移动到城市 $2$（或城市 $5$）。 - 第 $7$ 个查询：
1 1 6。他们可以选择 $X = 3$ 并移动，使得最终城市为城市 $4$（经济价值为 $11$）和城市 $1$（经济价值为 $10$）。