To your surprise, Jamie is the final boss! Ehehehe.

Jamie has given you a tree with n vertices, numbered from 1 to n. Initially, the root of the tree is the vertex with number 1. Also, each vertex has a value on it.

Jamie also gives you three types of queries on the tree:

1 v — Change the tree's root to vertex with number v.

2 u v x — For each vertex in the subtree of smallest size that contains u and v, add x to its value.

3 v — Find sum of values of vertices in the subtree of vertex with number v.

A subtree of vertex v is a set of vertices such that v lies on shortest path from this vertex to root of the tree. Pay attention that subtree of a vertex can change after changing the tree's root.

Show your strength in programming to Jamie by performing the queries accurately!

Input

The first line of input contains two space-separated integers n and q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) — the number of vertices in the tree and the number of queries to process respectively.

The second line contains n space-separated integers a1, a2, ..., an ( - 108 ≤ ai ≤ 108) — initial values of the vertices.

Next n - 1 lines contains two space-separated integers ui, vi (1 ≤ ui, vi ≤ n) describing edge between vertices ui and vi in the tree.

The following q lines describe the queries.

Each query has one of following formats depending on its type:

1 v (1 ≤ v ≤ n) for queries of the first type.

2 u v x (1 ≤ u, v ≤ n, - 108 ≤ x ≤ 108) for queries of the second type.

3 v (1 ≤ v ≤ n) for queries of the third type.

All numbers in queries' descriptions are integers.

The queries must be carried out in the given order. It is guaranteed that the tree is valid.

Output

For each query of the third type, output the required answer. It is guaranteed that at least one query of the third type is given by Jamie.

Examples

Input

6 7
1 4 2 8 5 7
1 2
3 1
4 3
4 5
3 6
3 1
2 4 6 3
3 4
1 6
2 2 4 -5
1 4
3 3


Output

27
19
5


Input

4 6
4 3 5 6
1 2
2 3
3 4
3 1
1 3
2 2 4 3
1 1
2 2 4 -3
3 1


Output

18
21

Note

The following picture shows how the tree varies after the queries in the first sample. 

<image>
#include <bits/stdc++.h>
const int N = 100050;
long long addv[N * 4], sumv[N * 4];
inline void upd(int o, int l, int r) {
  if (l != r)
    sumv[o] = sumv[o << 1] + sumv[o << 1 | 1] + addv[o] * (r - l + 1);
  else
    sumv[o] = addv[o];
}
void add(int o, int l, int r, int L, int R, int x) {
  if (r < L || R < l) return;
  if (L <= l && r <= R) {
    addv[o] += x;
  } else {
    int mid = (l + r) >> 1;
    add(o << 1, l, mid, L, R, x);
    add(o << 1 | 1, mid + 1, r, L, R, x);
  }
  upd(o, l, r);
}
long long query(int o, int l, int r, int L, int R) {
  if (r < L || R < l) return 0;
  if (L <= l && r <= R) return sumv[o];
  int mid = (l + r) >> 1;
  return addv[o] * (std::min(r, R) - std::max(l, L) + 1) +
         query(o << 1, l, mid, L, R) + query(o << 1 | 1, mid + 1, r, L, R);
}
int n, q;
int pre[N], to[N * 2], nxt[N * 2], cnt;
inline void addEdge(int x, int y) {
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
}
int left[N], right[N], cnt2;
int a[N], root;
int fa[N][20], dep[N];
void dfs(int x, int f) {
  dep[x] = dep[f] + 1;
  fa[x][0] = f;
  for (int i = 0; fa[x][i]; ++i) fa[x][i + 1] = fa[fa[x][i]][i];
  left[x] = ++cnt2;
  add(1, 1, n, left[x], left[x], a[x]);
  for (int i = pre[x]; ~i; i = nxt[i])
    if (to[i] != f) dfs(to[i], x);
  right[x] = cnt2;
}
int LCA(int x, int y) {
  if (dep[x] < dep[y]) std::swap(x, y);
  for (int i = 19; ~i; --i)
    if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
  for (int i = 19; ~i; --i)
    if (fa[x][i] != fa[y][i]) {
      x = fa[x][i];
      y = fa[y][i];
    }
  return x == y ? x : fa[x][0];
}
void addS(int u, int v, int x) {
  int l1 = LCA(u, v), l2 = LCA(u, root), l3 = LCA(v, root);
  if (dep[l1] > std::max(dep[l3], dep[l2]))
    add(1, 1, n, left[l1], right[l1], x);
  else {
    add(1, 1, n, 1, n, x);
    if (l2 != root && l3 != root) {
      int t = root;
      for (int i = 19; ~i; --i)
        if (dep[fa[t][i]] > std::max(dep[l2], dep[l3])) t = fa[t][i];
      add(1, 1, n, left[t], right[t], -x);
    }
  }
}
long long queryS(int u) {
  if (u == root) return query(1, 1, n, 1, n);
  if (LCA(u, root) == u) {
    int t = root;
    for (int i = 19; ~i; --i)
      if (dep[fa[t][i]] > dep[u]) t = fa[t][i];
    return query(1, 1, n, 1, n) - query(1, 1, n, left[t], right[t]);
  }
  return query(1, 1, n, left[u], right[u]);
}
int main() {
  scanf("%d%d", &n, &q);
  memset(pre, -1, sizeof pre);
  int x, y;
  cnt = cnt2 = 0;
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i < n; ++i) {
    scanf("%d%d", &x, &y);
    addEdge(x, y);
    addEdge(y, x);
  }
  dfs(root = 1, 0);
  int op, u, v;
  while (q--) {
    scanf("%d%d", &op, &u);
    if (op == 1)
      root = u;
    else if (op == 2) {
      scanf("%d%d", &v, &x);
      addS(u, v, x);
    } else
      printf("%I64d\n", queryS(u));
  }
  return 0;
}
