题目背景

小 A 和小 B 正在玩一个有趣的电脑游戏。

题目描述

游戏在一棵大小为 $n$ 的树上进行。其中每个点都有点权，第 $i$ 个点的点权为 $w_i$。

每一次系统会给出一条链，小 A 可以从这条链上找出两个点权不同的点 $x,y$，他的得分是 $w_x\bmod w_y$。然后小 B 会从整棵树中选取两个小 A 没有选过的点，计分方式同小 A。

为了保持游戏难度，系统有时会增加一个点的权值。

当然，小 A 会尽可能使自己得分最大，他想知道这个值是多少。同时，他想知道，在自己得分最大的情况下，小 B 的最大得分是多少。

输入格式

第一行一个整数 $n$ 表示树的节点个数。

接下来 $n-1$ 行，每行两个整数 $a,b$，表示 $a,b$ 之间有一条边。

接下来一行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个点的点权。

接下来一行一个整数 $q$。

接下来 $q$ 行，每行三个整数 $opt,x,y$。

若 $opt=0$，将 $w_x$ 增加 $y$。

若 $opt=1$，表示系统给出一条从 $x$ 到 $y$ 的链。

输出格式

对于每一次 $opt=1$，输出一行两个整数 $suma,sumb$ 。分别表示小 A 的最大得分和在这情况下小 B 的最大得分 。

如果小 A 无法选出两个权值不同的点，那么只输出一个数 $-1$。

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

3 4
4 3
4 3
1 4
-1

提示

样例解释：

第一次：小 A 选择点 $3$ 和点 $2$，得分为 $3\bmod 4=3$，小 B 选择点 $6$ 和点 $1$ 得分为 $4\bmod 5=4$。

第二次：小 A 选择点 $2$ 和点 $1$，得分为 $4\bmod 5=4$，小 B 选择点 $7$ 和点 $6$ 得分为 $3\bmod 4=3$。

第三次：小 A 选择点 $2$ 和点 $1$，得分为 $4\bmod 5=4$，小 B 选择点 $7$ 和点 $6$ 得分为 $3\bmod 4=3$。

第四次：第 $2$ 个点点权变为 $5$。

第五次：小 A 选择点 $5$ 和点 $1$，得分为 $1\bmod 5=1$，小 B 选择点 $6$ 和点 $2$ 得分为 $4\bmod 5=4$。

第六次：小 A 可以选的点只有 $1,2$ ，点权都是 $5$，没有可以选的方案。

本题采用捆绑测试。 | Subtasks |$n,q$ |特殊性质 |分数 | | :----------: | :----------: | :----------: | :----------: | |Subtask1 |$\leq10^3$ |无 |$10$ | |Subtask2 |$\leq10^5$ |树的形态，点权随机 |$15$ | |Subtask3 |$\leq10^5$ |最多有 $5$ 种不同的点权，且没有修改 |$15$ | |Subtask4 |$\leq10^5$ |树为一条链，且第 $i$$(i>1)$ 个点的父亲为 $i-1$ |$25$ | |Subtask5 |$\leq10^5$ |无 |$35$ |

对于所有数据 $1 \leq n,q \leq 10^5$，$1 \leq w_i \leq 10^4$，增加的数为不大于 $10^3$ 的正整数，且输入为一棵合法的树。保证任何时候不同种类的数大于等于 $4$。