#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define clr(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define readll(x) scanf("%I64d",&x)
#define mod 1000000007
#define eps 1e-6
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 50002, MOD = 1009;
int n,q,t,a[N],start[N],endd[N],node[N];
char s[10];

int T[N],per[N][17],L[N];
vi adjL[N];
bool vis[N];

void dfs(int x, int level){
    start[x] = ++t;
    node[t] = x;
    vis[x] = true;
    lp(i,0,adjL[x].size()-1){
        int child = adjL[x][i];
        if(!vis[child]){
            T[child] = x;
            L[child] = level+1;
            dfs(child,level+1);
        }
    }
    endd[x] = t;
}

void Root(int root){
    T[root] = root;
    L[root] = 1;
    dfs(root,1);

    lp(i,1,n)
        for (int j = 0; (1ll<<j) < n; j++)
            per[i][j] = -1;

      lp(i,1,n) per[i][0] = T[i];

      for (int j = 1; (1ll<<j) < n; j++)
         lp(i,1,n)
             if (per[i][j-1] != -1)
                 per[i][j] = per[per[i][j-1]][j-1];
}

int query(int p, int q){
      if (L[p] < L[q]) swap(p,q);

      int log;
      for (log = 1; (1ll<<log) <= L[p]; log++);
      log--;

     lpd(i,log,0)
          if (L[p] - (1ll << i) >= L[q])
              p = per[p][i];

      if (p == q) return p;

      for (int i = log; i >= 0; i--)
          if (per[p][i] != -1 && per[p][i] != per[q][i])
              p = per[p][i], q = per[q][i];

      return T[p];
}

void divide(int u, int v, int w){
    int lca = query(u,v);
    a[lca] = a[lca]/w + (a[lca]%w != 0);
    while(u != lca) a[u] = a[u]/w + (a[u]%w != 0), u = T[u];
    while(v != lca) a[v] = a[v]/w + (a[v]%w != 0), v = T[v];
}

int solve(int k, int w){
    int ret = 0;
    lp(i,st[k],ed[k]) ret = max(ret, w ^ a[node[i]]);
    return ret;
}

int main(){
    scanf("%d%d",&n,&q);
    lp(i,1,n) scanf("%d",&a[i]);

    lp(i,1,n-1){
        int x,y;
        scanf("%d%d",&x,&y);
        adjL[x].pb(y);
        adjL[y].pb(x);
    }

    Root(1);

    while(q--){
        scanf("%s",s);
        if(s[0] == 'D'){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            divide(u,v,w);
        }
        else{
            int k,w;
   			scanf("%d%d",&k,&w);
            if(s[0] == 'M') a[k] = a[k] * w % MOD;
            else printf("%d\n", solve(k,w));
        }
    }
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);
*/