【題目描述】

 You're given a tree on N vertices. Each vertex has a positive integer written on it, number on the ith vertex being vi. Your program must process two types of queries :1. Find query represented by F u v : Find out gcd of all numbers on the unique path between vertices u and v in the tree (both inclusive).2. Change query represented by C u v d : Add d to the number written on all vertices along the unique path between vertices u and v in the tree (both inclusive).

Input

First line of input contains an integer N denoting the size of the vertex set of the tree. Then follow N - 1 lines, ith of which contains two integers ai and bi denoting an edge between vertices ai and bi in the tree. After this follow N space separated integers in a single line denoting initial values vi at each of these nodes. Then follows a single integer Q on a line by itself, denoting the number of queries to follow. Then follow Q queries, each one on a line by itself. Each query is either a find query or a change query with format as given in problem statement. Note that all vertices are 0-based.

Output

For every find query, print the answer to that query in one line by itself.

Example

Input:

6
0 4
0 5
1 5
5 2
3 5
3 1 3 2 4 2
5
F 3 5
C 1 3 1
C 3 4 4
F 3 0
F 2 5

Output:

2
7
1

Constraints

1 <= N <= 50000
1 <= Q <= 50000
0 <= u, v <= N-1
1 <= vi <= 10^4
0 <= d <= 10^4 

【題目分析】
歷經一天我終于搞出這道題了。其實用半天寫了代碼，但是另外半天都在調，因為用位操作符的時候少寫了一個小于好導致數組越界發生玄學錯誤，我愣是研究了一下午加一晚上都沒有發現，各種調試覺得是電腦出問題了，我明明沒有修改那個數組的值但是他的值莫名其妙就改了。。。
今天早上發現這個錯誤后直接A了。
自己看的時候還是不會，覺得就算用樹鏈剖分用線段樹維護區間GCD可是人家還有區間修改怎么辦，總不能區間修改以后暴力維護一遍區間GCD吧。學習了一下其他大佬的博客后發現一個比較有（xuan）趣（xue）的結論：$gcd(x1,x2,x3...)=gcd(x1,x2?x1,x3?x2,...)$
然后我們就發現區間GCD和差分結合在一起啦啦啦啦。對于每一個區間，我們進行一次單點查詢x1,再進行一次區間查詢后面的維護的GCD。即$gcd(x1,x2,x3...)=gcd(val1[x1],val2[x2..xn])$，其中val2維護的是差分區間的GCD值，val1維護的是原來的數值。
這樣做的意義就是讓區間修改變成單點修改：對于每次區間修改，我們發現對于差分區間內部來講其實只改變了第一個的值，其他的都沒有改變（大家都增加了，減掉后值就沒有改變）。
為了每次方便查詢，我們用兩個樹鏈分別維護原來的值和差分的值，查詢的時候分別對兩個進行單點查詢和區間查詢。
每次修改我們對原來的值的樹鏈進行區間修改，對維護差分GCD的樹鏈進行單點修改：這個和我們進行儲存的方式息息相關，在這里我們是從重鏈往下，將兒子節點的值進行差分（父親節點-兒子節點）(理解這個十分重要)。因此如果我們修改一個區間，重鏈的頭節點的值會增加val（因為沒有什么減他），修改的區間在這條鏈的最后的節點的兒子節點（如果有的話）會增加val（因為最后的節點的值增加了，兒子節點的值為最后節點減去兒子節點），如果區間沒有到達重鏈的頭節點，那么區間最前面的點的值會減小val（因為他的值應該是父親節點減去他，他的值增加而父親節點的值沒有變化所以他的值要減小val）。可能一開始還是有些難以理解（我理解了半天），可以對照著代碼。代碼應該還是比較清晰的。（注意區間修改是val1區間，單點修改是val2區間，區間查詢是val2區間，單點查詢是val1區間）
【AC代碼】

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=5e4+5;
int head[MAXN],fa[MAXN],pos[MAXN],A[MAXN];
int a[MAXN],sz[MAXN],son[MAXN],deep[MAXN],top[MAXN];
struct node
{int v,next;
}Edge[MAXN<<1];
int tot=0,cnt=0;
int n,m;
int val1[MAXN<<2],add[MAXN<<2],val2[MAXN<<2];void AddEdge(int u,int v)
{tot++;Edge[tot].v=v; Edge[tot].next=head[u];head[u]=tot;
}void dfs1(int u,int f)
{fa[u]=f; deep[u]=deep[f]+1;son[u]=0; sz[u]=1;for(int i=head[u];i;i=Edge[i].next){int v=Edge[i].v;if(v!=f){dfs1(v,u);sz[u]+=sz[v];if(sz[son[u]]<sz[v]) son[u]=v;}}
}void dfs2(int u,int f,int k)
{top[u]=k; pos[u]=++cnt; A[cnt]=a[u];if(!son[u]) return;if(son[u]) dfs2(son[u],u,k);for(int i=head[u];i;i=Edge[i].next){int v=Edge[i].v;if(v!=f && v!=son[u]) dfs2(v,u,v);}
}void test()
{for(int i=1;i<13;i++){printf("%d ",add[i]);}printf("%d\n",add[13]);
}void Build(int k,int l,int r)
{add[k]=0;if(l==r){val1[k]=A[l];return;}int mid=(l+r)>>1;Build(k<<1,l,mid);Build(k<<1|1,mid+1,r);
}int gcd(int a,int b)
{return b?gcd(b,a%b):abs(a);
}void change_point(int k,int l,int r,int x,int val)
{if(l==r){val2[k]+=val;return;}int mid=(l+r)>>1;if(x<=mid) change_point(k<<1,l,mid,x,val);else change_point(k<<1|1,mid+1,r,x,val);val2[k]=gcd(val2[k<<1],val2[k<<1|1]);
}void pushdown(int k)
{if(add[k]){add[k<<1]+=add[k]; add[k<<1|1]+=add[k];val1[k<<1]+=add[k]; val1[k<<1|1]+=add[k];add[k]=0;}
}void change_interval(int k,int l,int r,int L,int R,int val)
{if(l>=L && r<=R){add[k]+=val;val1[k]+=val;return;}int mid=(l+r)>>1;pushdown(k);if(L<=mid) change_interval(k<<1,l,mid,L,R,val);if(R>mid) change_interval(k<<1|1,mid+1,r,L,R,val);
}void change_tree(int u,int v,int w)
{while(top[u]!=top[v]){if(deep[top[u]]<deep[top[v]]) swap(u,v);change_interval(1,1,n,pos[top[u]],pos[u],w);if(son[u]) change_point(1,1,n,pos[son[u]],w);u=fa[top[u]];}if(deep[u]<deep[v]) swap(u,v);change_interval(1,1,n,pos[v],pos[u],w);if(son[u]) change_point(1,1,n,pos[son[u]],w);if(son[fa[v]]==v) change_point(1,1,n,pos[v],-w);
}int query_interval(int k,int l,int r,int L,int R)
{if(l>=L && r<=R){return val2[k];}int mid=(l+r)>>1;if(R<=mid) return query_interval(k<<1,l,mid,L,R);else if(L>mid) return query_interval(k<<1|1,mid+1,r,L,R);else return gcd(query_interval(k<<1,l,mid,L,mid),query_interval(k<<1|1,mid+1,r,mid+1,R));
}int query_point(int k,int l,int r,int x)
{if(l==r && l==x){return val1[k];}int mid=(l+r)>>1;pushdown(k);if(x<=mid) return query_point(k<<1,l,mid,x);else return query_point(k<<1|1,mid+1,r,x);
}int query_tree(int u,int v)
{int ret=0;while(top[u]!=top[v]){if(deep[top[u]]<deep[top[v]]) swap(u,v);if(top[u]!=u) ret=gcd(ret,query_interval(1,1,n,pos[son[top[u]]],pos[u]));ret=gcd(ret,query_point(1,1,n,pos[top[u]]));u=fa[top[u]];}if(deep[u]<deep[v]) swap(u,v);if(u!=v) ret=gcd(ret,query_interval(1,1,n,pos[son[v]],pos[u]));ret=gcd(ret,query_point(1,1,n,pos[v]));return ret;
}void Read()
{int u,v;scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d%d",&u,&v);AddEdge(u+1,v+1); AddEdge(v+1,u+1);}for(int i=1;i<=n;i++) scanf("%d",&a[i]);// test();
}void Init()
{dfs1(1,0); dfs2(1,0,1);Build(1,1,n);for(int i=1;i<=n;i++){if(son[i])change_point(1,1,n,pos[son[i]],a[i]-a[son[i]]);}
}void Solve()
{char cmd[10];int u,v,w;scanf("%d",&m);while(m--){scanf("%s",cmd);if(cmd[0]=='F'){scanf("%d%d",&u,&v);printf("%d\n",query_tree(u+1,v+1));}else{scanf("%d%d%d",&u,&v,&w);change_tree(u+1,v+1,w);}}
}int main()
{Read();Init();Solve();return 0;
}