1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 #include <set>
5 #define N 2000010
6 using namespace std;
7 struct edge {int to,from;}e[N*2],a[N*2];
8 int n,m,v[N],num1,num2,cnt,cnt1,dfn[N],low[N],head[N],last[N],top[N],dep[N],fa[N],size[N],son[N],l[2*N][2],p[2*N],tree[N],n2,mn[2*N],q[N];
9 multiset<int>Q[N];
10 using namespace std;
11 void insert(int x,int y) { e[++cnt].to=y; e[cnt].from=head[x]; head[x]=cnt; }
12 void insert1(int x,int y) { a[++cnt1].to=y; a[cnt1].from=last[x]; last[x]=cnt1; }
13 void tarjan(int x,int fa)
14 {
15 q[++q[0]]=x,dfn[x]=low[x]=++dfn[0];
16 for (int i=head[x];i;i=e[i].from)
17 if (e[i].to!=fa)
18 {
19 if (!dfn[e[i].to])
20 {
21 tarjan(e[i].to,x);
22 if (low[e[i].to]>=dfn[x])
23 {
24 insert1(++num1,x),insert1(x,num1);
25 while (q[q[0]]!=e[i].to) insert1(num1,q[q[0]]),insert1(q[q[0]],num1),q[q[0]--]=0;
26 insert1(num1,e[i].to),insert1(e[i].to,num1),q[q[0]--]=0;
27 }
28 else low[x]=min(low[x],low[e[i].to]);
29 }
30 else low[x]=min(low[x],dfn[e[i].to]);
31 }
32 }
33 void dfs(int x,int pre)
34 {
35 dep[x]=dep[pre]+1,fa[x]=pre,size[x]=1;
36 if (x<=n&&pre>n) Q[pre].insert(v[x]);
37 for (int i=last[x];i;i=a[i].from)
38 if (a[i].to!=pre)
39 {
40 dfs(a[i].to,x),size[x]+=size[a[i].to];
41 if (size[a[i].to]>size[son[x]]) son[x]=a[i].to;
42 }
43 }
44 void build(int d,int x,int y)
45 {
46 mn[d]=1e9;
47 if (x==y) { tree[x]=d; return; }
48 int mid=(x+y)>>1;
49 p[l[d][0]=++num2]=d,build(num2,x,mid);
50 p[l[d][1]=++num2]=d,build(num2,mid+1,y);
51 }
52 void add(int x,int y)
53 {
54 mn[x]=y,x=p[x];
55 while (x) mn[x]=min(mn[l[x][0]],mn[l[x][1]]),x=p[x];
56 }
57 void dfs1(int x)
58 {
59 if (!x) return;
60 dfn[x]=++dfn[0];
61 if (x>n) v[x]=*Q[x].begin();
62 add(tree[dfn[x]],v[x]);
63 top[son[x]]=top[x],dfs1(son[x]);
64 for (int i=last[x];i;i=a[i].from)
65 if (a[i].to!=fa[x]&&a[i].to!=son[x])
66 top[a[i].to]=a[i].to,dfs1(a[i].to);
67 }
68 int query(int d,int L,int R,int x,int y)
69 {
70 if (!d||x>y||x>R||y<L) return 1e9;
71 if (x<=L&&R<=y) return mn[d];
72 int mid=(L+R)>>1;
73 return min(query(l[d][0],L,mid,x,y),query(l[d][1],mid+1,R,x,y));
74 }
75 int work(int x,int y)
76 {
77 if (top[x]==top[y])
78 {
79 if (dep[x]>dep[y]) swap(x,y);
80 int k=1e9;
81 if (x>n) k=v[fa[x]];
82 return min(k,query(1,1,num1,dfn[x],dfn[y]));
83 }
84 if (dep[top[x]]>dep[top[y]]) swap(x,y);
85 return min(work(x,fa[top[y]]),query(1,1,num1,dfn[top[y]],dfn[y]));
86 }
87 int main()
88 {
89 freopen("paoshang.in","r",stdin),freopen("paoshang.out","w",stdout);
90 scanf("%d%d",&n,&m);
91 for (int i=1;i<=n;i++) scanf("%d",&v[i]);
92 for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),insert(x,y),insert(y,x);
93 num1=n,tarjan(1,0);
94 dfs(1,0);
95 num2=1,build(1,1,num1);
96 memset(dfn,0,sizeof(dfn)),dfs1(1);
97 int x,y,o;
98 scanf("%d",&o);
99 while (o--)
100 {
101 scanf("
");
102 char ch=getchar();
103 scanf("%d%d",&x,&y);
104 if (ch=='Q') printf("%d
",v[x]-work(x,y));
105 else
106 {
107 add(tree[dfn[x]],y);
108 if (x>1)
109 {
110 int k=fa[x];
111 Q[k].erase(Q[k].find(v[x])),Q[k].insert(y);
112 int o=*Q[k].begin();
113 if (v[k]!=o) v[k]=o,add(tree[dfn[k]],v[k]);
114 }
115 v[x]=y;
116 }
117 }
118 }