测试数据来自 system/1936

描述

这是一个太阳从西边升起的情人节，木姑娘邀请我一起去逛街。

城市道路被描绘成一个树形结构，由n个路口组成。

今天实在是太反常了，每一个路口都被挂起来了一盏可变色的灯笼，其中有些是红色的灯笼，有些是蓝色的灯笼。

一个奇怪的政策，仅限于今天，要求在路口u的人群，只能移动到所有同色的路口v，且u到v的道路上所有路口也都有着相同颜色的灯笼。

每一处路口都被赋予了权值w[i]，诠释了这个路口对于木姑娘的吸引力。

带木姑娘去那些最吸引她的路口，就是今天白天的任务。

格式

输入格式

第一行给出路口数n，1<=n<=100000。
之后n-1行，每行给出两个数(u,v)描绘了一条连接u和v的道路。1<=u,v<=n。
之后1行，给出了n个0或1的整数，表示了每一个路口灯笼的颜色。
之后1行，给出了n个整数w[1],w[2],...,w[n]表示了每一个路口的权值。
再下面一行，给出整数m，表示询问和修改的总数，1<=m<=100000。
之后m行，每行提供一条询问，或修改操作，满足下述三种形式：
0 u : 询问从路口u出发，可以到达的最有吸引力的路口。
1 u : 修改路口u的灯笼颜色。
2 u w : 将路口u的权值修改为w。

输出格式

对于每一次询问，输出目标路口的权值。（即可以抵达的有着最大权值的路口的权值）

样例1

样例输入1

5
1 2
1 3
1 4
1 5
0 1 1 1 1
1 2 3 4 5
3
0 1
1 1
0 1

样例输出1

1
5

样例2

样例输入2

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

样例输出2

7
5
7

限制

对于30％的数据，n,m<=10。
存在40％的数据，n,m<=100000，城市交通网形成的树结构的高度不超过256。
对于100％的数据，n,m<=100000，所有权值为绝对值不超过1000000000的整数。