nodgd觉得计算最大公约数非常容易，于是向p6pou发起挑战。

p6pou不甘示弱，掏出一棵树，每个节点上有一个整数。p6pou每次可能会修改一条链上的整数，或者让nodgd计算一条链上所有整数的最大公约数。

nodgd即使是口算也算得很快，但p6pou却需要借助计算机。请你帮p6pou写个程序来计算。

输入格式

第一行一个整数 \(N\) ，表示树上节点数。
接下来 \(N-1\) 行，每行两个整数 \(u,v\) ，表示一条边。
接下来一行 \(N\) 个整数，表示每个节点的初始权值。
接下来一个整数 \(Q\) ，表示操作的次数。

• F u v ：p6pou想知道节点 \(u,v\) 链上的最大公约数。
• C u v d ：p6pou修改了节点 \(u,v\) 链上的整数，将每个数都增加了 \(d\) 。

第一行一个整数 \(N\) ，表示树上节点数。
接下来 \(N-1\) 行，每行两个整数 \(u,v\) ，表示一条边。
接下来一行 \(N\) 个整数，表示每个节点的初始权值。
接下来一个整数 \(Q\) ，表示操作的次数。

• F u v ：p6pou想知道节点 \(u,v\) 链上的最大公约数。
• C u v d ：p6pou修改了节点 \(u,v\) 链上的整数，将每个数都增加了 \(d\) 。

每次操作 F 输出一行一个整数答案。

对于100%的数据
$1\leq N\leq 50000$ ， $1\leq Q\leq 50000$
$0\leq u,v\leq N-1$ ， $1\leq v_i\leq 10^4$ ， $0\leq d\leq 10^4$