Description

一棵树有$N$ 个节点，每个节点都有一个权值$W$$i$ ，有$4$种操作： ①$1$ $x$ $y$ ，在两个节点$x$、$y$ 之间添加一条新边。因此，在这种操作之后，两棵树将连接成一棵新树；

②$2$ $x$ $y$ ，在树集合中找到包含节点$x$ 的树，并且使节点$x$ 成为该树的根，然后删除节点$y$ 与其父节点之间的边。在这种操作之后，一棵树将被分成两部分；

③$3$ $w$ $x$ $y$ ，将$x$ 到$y$ 路径上所有节点的权值都增加$w$ ；④$4$ $x$ $y$。

Format

Input

包含多个测试用例。

每个测试用例的第$1$行都包含一个整数$N$ $（$$1$$≤$$N$ $≤$$3$×$10^5$ $）$；

接下来的$N$ -$1$行，每行都包含两个整数$x$、$y$，表示它们之间有一条边；

下一行包含$N$ 个整数，表示每个节点的权值都为$W$$i$ $（$$0$$≤$$W$$i$ $≤$$3$$0$$0$$0$$）$；

再下一行包含一个整数$Q$ $（$$1$$≤$$Q$ $≤$$3$×$10^5$$）$。

Output

对每个查询，都单行输出正确答案。若此查询是特殊操 作，则输出$-1$。

在每个测试用例之后都输出一个空行。

Samples

5
1 2
2 4
2 5
1 3
1 2 3 4 5
6
4 2 3
2 1 2
4 2 3
1 3 5
3 2 1 4
4 1 4

3
-1
7

来源

HDU4010