#include<cstdio>
const int N=30010,M=65540,V=128+1,P=10007,INV=(P+1)/2;
char op[9];
int n,m,Q,i,j,x,y,g[N],v[N<<1],nxt[N<<1],ed,inv[P];
int size[N],f[N],son[N],top[N],bottom[N],loc[N],q[N],dfn;
int a[N][V],dp[N][V],h[N][V],c[N][V],ans[V],ret[V];
struct E{int sum[V],pre[V],suf[V],mul[V];}val[M],tmp;
bool flag;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void FWT(int*a,int n){
  for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){
    int x=a[i+j],y=a[i+j+d];
    a[i+j]=(x+y)%P;
    a[i+j+d]=(x-y+P)%P;
  }
}
inline void UFWT(int*a,int n){
  for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){
    int x=a[i+j],y=a[i+j+d];
    a[i+j]=(x+y)*INV%P;
    a[i+j+d]=(x-y+P)*INV%P;
  }
}
void dfs(int x){
  size[x]=1;
  for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){
    f[v[i]]=x;
    dfs(v[i]);
    size[x]+=size[v[i]];
    if(size[v[i]]>size[son[x]])son[x]=v[i];
  }
}
void dfs2(int x,int y){
  q[loc[x]=++dfn]=x;
  top[x]=y;
  bottom[y]=x;
  if(son[x])dfs2(son[x],y);
  for(int i=0;i<m;i++)h[x][i]=1,c[x][i]=0;
  for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]&&v[i]!=son[x]){
    int u=v[i];
    dfs2(u,u);
    for(int j=0;j<m;j++){
      if(dp[u][j]+1<P)h[x][j]=h[x][j]*(dp[u][j]+1)%P;
      else c[x][j]++;
    }
  }
  for(int i=0;i<m;i++){
    if(c[x][i])dp[x][i]=0;
    else dp[x][i]=a[x][i]*h[x][i]%P*(dp[son[x]][i]+1)%P;
    ans[i]=(ans[i]+dp[x][i])%P;
  }
}
inline void init(E&x,int p){
  for(int i=0;i<m;i++){
    if(c[p][i])x.sum[i]=x.pre[i]=x.suf[i]=x.mul[i]=0;
    else x.sum[i]=x.pre[i]=x.suf[i]=x.mul[i]=a[p][i]*h[p][i]%P;
  }
}
inline void merge(E&f,const E&l,const E&r){
  for(int i=0;i<m;i++){
    f.sum[i]=(l.sum[i]+r.sum[i]+l.suf[i]*r.pre[i])%P;
    f.pre[i]=(l.pre[i]+l.mul[i]*r.pre[i])%P;
    f.suf[i]=(r.suf[i]+r.mul[i]*l.suf[i])%P;
    f.mul[i]=l.mul[i]*r.mul[i]%P;
  }
}
void build(int x,int a,int b){
  if(a==b){init(val[x],q[a]);return;}
  int mid=(a+b)>>1;
  build(x<<1,a,mid),build(x<<1|1,mid+1,b);
  merge(val[x],val[x<<1],val[x<<1|1]);
}
void change(int x,int a,int b,int c){
  if(a==b){init(val[x],q[a]);return;}
  int mid=(a+b)>>1;
  if(c<=mid)change(x<<1,a,mid,c);else change(x<<1|1,mid+1,b,c);
  merge(val[x],val[x<<1],val[x<<1|1]);
}
void ask(int x,int a,int b,int c,int d){
  if(c<=a&&b<=d){
    if(!flag)tmp=val[x],flag=1;
    else merge(tmp,tmp,val[x]);
    return;
  }
  int mid=(a+b)>>1;
  if(c<=mid)ask(x<<1,a,mid,c,d);
  if(d>mid)ask(x<<1|1,mid+1,b,c,d);
}
inline void modify(int x){
  while(x){
    int y=f[top[x]];
    flag=0;
    ask(1,1,n,loc[top[x]],loc[bottom[top[x]]]);
    for(int i=0;i<m;i++)ans[i]=(ans[i]-tmp.sum[i]+P)%P;
    if(y)for(int i=0;i<m;i++){
      if(tmp.pre[i]+1<P)h[y][i]=h[y][i]*inv[tmp.pre[i]+1]%P;
      else c[y][i]--;
    }
    change(1,1,n,loc[x]);
    flag=0;
    ask(1,1,n,loc[top[x]],loc[bottom[top[x]]]);
    for(int i=0;i<m;i++)ans[i]=(ans[i]+tmp.sum[i])%P;
    if(y)for(int i=0;i<m;i++){
      if(tmp.pre[i]+1<P)h[y][i]=h[y][i]*(tmp.pre[i]+1)%P;
      else c[y][i]++;
    }
    x=y;
  }
}
int main(){
  for(inv[0]=inv[1]=1,i=2;i<P;i++)inv[i]=(P-inv[P%i])*(P/i)%P;
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++){
    scanf("%d",&x);
    for(j=0;j<m;j++)a[i][j]=0;
    a[i][x]=1;
    FWT(a[i],m);
  }
  for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
  dfs(1);
  dfs2(1,1);
  build(1,1,n);
  scanf("%d",&Q);
  while(Q--){
    scanf("%s%d",op,&x);
    if(op[0]=='C'){
      scanf("%d",&y);
      for(i=0;i<m;i++)a[x][i]=0;
      a[x][y]=1;
      FWT(a[x],m);
      modify(x);
    }else{
      for(i=0;i<m;i++)ret[i]=ans[i];
      UFWT(ret,m);
      printf("%d\n",ret[x]);
    }
  }
  return 0;
}

#pragma G++ optimize(2)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define O4 __inline__ __attribute__((always_inline))
#define inf 0x7fffffff
#define UL unsigned LL
#define LD long double
#ifdef ONLINE_JUDGE
#define getchar nc
#endif
//#define int LL
namespace FastIO{
    O4 char nc(){
        static char buf[100000],*p1=buf,*p2=buf;
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
    }
    O4 int read(){
        char t;int u=0,k=1;t=getchar();
        while(t<'0'||t>'9'){if(t=='-')k=-1;t=getchar();}
        while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
        return u*k;
    }
    template <typename T>
    O4 void read(T &u){
        char t;T k=1;u=0;t=getchar();
        while(t<'0'||t>'9'){if(t=='-')k=-1;t=getchar();}
        while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
        if(t=='.'){
            T mass=0.1;t=getchar();
            while(t>='0'&&t<='9'){u+=mass*(t-'0');mass/=10;t=getchar();}
        }u*=k;
    }
    O4 int read(char asd[]){
        char t=getchar();int u=0;
        while(t==' '||t=='\n'||t=='\r')t=getchar();
        if(t==EOF)return -1;
        while(t!=' '&&t!='\n'&&t!=EOF&&t!='\r')asd[u++]=t,t=getchar();
        asd[u]='\0';return u;
    }
    char sr[1<<23],z[23];int C=-1,Z;
    O4 void wer(int x,char T){
        int y=0;if(x<0)y=1,x=-x;
        while(z[++Z]=x%10+'0',x/=10);if(y)z[++Z]='-';
        while(sr[++C]=z[Z],--Z);sr[++C]=T;
    }
    O4 void wer(char T[],char QWQ){
        for(int i=0;T[i]!='\0';i++)sr[++C]=T[i];
        sr[++C]=QWQ;
    }
    O4 void out(){fwrite(sr,1,C+1,stdout);C=-1;}
}
using namespace std;
using namespace FastIO;
namespace whatever{
    const int mod=10007;
    const int inv_2=(mod+1)/2;
    vector<int> adj[30001];
    int heavy[30001];
    int size[30001];
    int father[30001];
    void dfs1(int cur, int father){
        size[cur]=1;
        heavy[cur]=-1;
        for(size_t i=0; i<adj[cur].size(); ++i){
            int to=adj[cur][i];
            if(to==father)
                continue;
            whatever::father[to]=cur;
            dfs1(to, cur);
            if(heavy[cur]==-1||size[heavy[cur]]<size[to])
                heavy[cur]=to;
            size[cur]+=size[to];
        }
    }
    struct node_type{
        node_type *left, *right;
        node_type *father;
        short result[128];
        short all[128];
        union{
            struct{
                short prefix[128];
                short suffix[128];
            };
            struct{
                short cnt[128];
                short all_without_cnt[128];
            };
        };
    };
    node_type nodes[30000*2];
    int node_cnt;
    node_type *allocate(){
        return &nodes[node_cnt++];
    }
    int init_value[30001];
    int light_size[30001];
    int prefix_sum[30001];
    int path[30001];
    node_type *root;
    int m;
    void push_up(node_type *cur){
        node_type *left=cur->left;
        node_type *right=cur->right;
        short *left_prefix=(left->left?left->prefix:left->all);
        short *right_suffix(right->left?right->suffix:right->all);
        short *left_suffix=(left->left?left->suffix:left->all);
        short *right_prefix=(right->left?right->prefix:right->all);
        #if 0//<-----------------------------
        for(int i=0; i<m; ++i)
            cur->prefix[i]=(left->prefix[i]+right->prefix[i]*left->all[i])%mod;
        for(int i=0; i<m; ++i)
            cur->suffix[i]=(right->suffix[i]+left->suffix[i]*right->all[i])%mod;
        for(int i=0; i<m; ++i)
            cur->all[i]=(left->all[i]*right->all[i])%mod;
        for(int i=0; i<m; ++i)
            cur->result[i]=(left->result[i]+right->result[i]+left->suffix[i]*right->prefix[i])%mod;
        #endif
        for(int i=0; i<m; ++i)
            cur->prefix[i]=(left_prefix[i]+right_prefix[i]*left->all[i])%mod;
        for(int i=0; i<m; ++i)
            cur->suffix[i]=(right_suffix[i]+left_suffix[i]*right->all[i])%mod;
        for(int i=0; i<m; ++i)
            cur->all[i]=(left->all[i]*right->all[i])%mod;
        for(int i=0; i<m; ++i)
            cur->result[i]=(left->result[i]+right->result[i]+left_suffix[i]*right_prefix[i])%mod;
    }
    int popcount_table[128];
    node_type *build(int first, int last){
        if(first==last){
            node_type *cur=&nodes[path[first]];
            //memcpy(cur->result, cur->all, sizeof(short)*m);
            //xxx
            int value=init_value[path[first]];
            for(int i=0; i<m; ++i){
                int sign=(popcount_table[value&i]&1?mod-1:1);
                cur->all_without_cnt[i]=cur->all_without_cnt[i]*sign%mod;
                if(cur->cnt[i])
                    cur->all[i]=0;
                else
                    cur->all[i]=cur->all_without_cnt[i];
                cur->result[i]=(cur->result[i]+cur->all[i])%mod;
            }
            return cur;
        }
        int mid=lower_bound(prefix_sum+first, prefix_sum+last-1, prefix_sum[first-1]+(prefix_sum[last]-prefix_sum[first-1])/2)-prefix_sum;
        assert(mid>=first);
        assert(mid<last);
        node_type *cur=allocate();
        cur->left=build(first, mid);
        cur->left->father=cur;
        cur->right=build(mid+1, last);
        cur->right->father=cur;
        push_up(cur);
        return cur;
    }
    int top[30001];
    void dfs2(int cur, int father){
        for(size_t i=0; i<adj[cur].size(); ++i){
            int to=adj[cur][i];
            if(to==father)
                continue;
            if(to==heavy[cur])
                continue;
            top[to]=to;
            dfs2(to, cur);
        }
        light_size[cur]=size[cur];
        if(heavy[cur]!=-1){
            light_size[cur]-=size[heavy[cur]];
            top[heavy[cur]]=top[cur];
            dfs2(heavy[cur], cur);
        }
        else{
            cur=top[cur];
            father=whatever::father[cur];
            int len=0;
            do{
                path[++len]=cur;
                prefix_sum[len]=prefix_sum[len-1]+light_size[cur];
                cur=heavy[cur];
            }
            while(cur!=-1);
            node_type *node=build(1, len);
            if(father==-1)
                root=node;
            else{
                node->father=&nodes[father];
                for(int i=0; i<m; ++i)
                    nodes[father].result[i]=(nodes[father].result[i]+node->result[i])%mod;
                if(node->left){
                    for(int i=0; i<m; ++i)
                        if(node->prefix[i]+1!=mod)
                            nodes[father].all_without_cnt[i]=nodes[father].all_without_cnt[i]*(node->prefix[i]+1)%mod;
                        else
                            ++nodes[father].cnt[i];
                }
                else{
                    for(int i=0; i<m; ++i)
                    //  if(node->all[i]+1!
                        if(node->all[i]+1!=mod)
                            nodes[father].all_without_cnt[i]=nodes[father].all_without_cnt[i]*(node->all[i]+1)%mod;
                        else
                            ++nodes[father].cnt[i];
                }
            }
        }
    }
    int inv[mod];
    void update_leaf(node_type *cur, short *old_result, short *new_result, short *old_prefix_or_all, short *new_prefix_or_all){
        assert(!cur->left);
        for(int i=0; i<m; ++i){
            if(old_prefix_or_all[i] +1/*<------------*/!=mod)
                cur->all_without_cnt[i]=cur->all_without_cnt[i]*inv[old_prefix_or_all[i] +1/*<------------*/]%mod;
            else{
                assert(cur->cnt[i]>0);
                --cur->cnt[i];
            }
            if(new_prefix_or_all[i] +1/*<------------*/!=mod)
                cur->all_without_cnt[i]=cur->all_without_cnt[i]*(new_prefix_or_all[i] +1/*<------------*/)%mod;
            else
                ++cur->cnt[i];
            int old_all=cur->all[i];
            if(cur->cnt[i])
                cur->all[i]=0;
            else
                cur->all[i]=cur->all_without_cnt[i];
            cur->result[i]=(cur->result[i]-old_all+cur->all[i]-old_result[i]+new_result[i]+mod*2)%mod;
        }
    }
    void run(){
        int n=read();m=read();
        for(int i=1; i<128; ++i)
            popcount_table[i]=popcount_table[i-(i&-i)]+1;
        inv[1]=1;
        for(int i=2; i<mod; ++i)
            inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        for(int i=1; i<=n; ++i)
            init_value[i]=read();
        for(int i=1; i<n; ++i){
            int a=read();
            int b=read();
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        father[1]=-1;
        dfs1(1, -1);
        top[1]=1;
        node_cnt=n+1;
        for(int i=1; i<=n; ++i)
            for(int j=0; j<m; ++j)
                nodes[i].all_without_cnt[j]=1;
        dfs2(1, -1);
        int q=read();//30000
        while(--q!=-1){
            char ch=getchar();
            while(!isupper(ch))
                ch=getchar();
            if(ch=='C'){//10000
                int x=read();
                int y=read();
                node_type *cur=&nodes[x];
                static short old_result[128];
                static short old_prefix_or_all[128];
                node_type *prev;
                while(cur){
                    if(cur->father&&!cur->father->left&&(cur->left||cur==&nodes[x])){
                        memcpy(old_result, cur->result, sizeof(short)*m);
                        memcpy(old_prefix_or_all, (cur==&nodes[x]?cur->all:cur->prefix), sizeof(short)*m);
                    }
                    if(cur==&nodes[x]){
                        int value=init_value[x];
                        for(int i=0; i<m; ++i){
                            if((popcount_table[value&i]&1)==(popcount_table[y&i]&1))
                                continue;
                            cur->all_without_cnt[i]=mod-cur->all_without_cnt[i];
                            if(cur->cnt[i])
                                continue;
                            cur->result[i]=(cur->result[i]-cur->all[i]*2+mod*2)%mod;
                            cur->all[i]=cur->all_without_cnt[i];
                        }
                    }
                    else if(cur->left)
                        push_up(cur);
                    else{
                        update_leaf(cur, old_result, prev->result, old_prefix_or_all, (prev==&nodes[x]?prev->all:prev->prefix));
                    }
                    prev=cur;
                    cur=cur->father;
                }
                init_value[x]=y;
            }
            else if(ch=='Q'){
                int k=read();
                int result=0;
                for(int i=0; i<m; ++i){
                    int sign=(popcount_table[i&k]&1?-1:1);
                    result+=root->result[i]*sign;
                }
                result=(result%mod+mod)%mod;
                result=result*inv[m]%mod;
                wer(result,'\n');
            }
            else
                assert(0);
        }
    }
}
int main(){
    whatever::run();out();
}