有趣的游戏

题目背景

小 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$。**

输入输出样例

输入样例 #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

输出样例 #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$。**