Iahub likes trees very much. Recently he discovered an interesting tree named propagating tree. The tree consists of n nodes numbered from 1 to n, each node i having an initial value ai. The root of the tree is node 1.

This tree has a special property: when a value val is added to a value of node i, the value -val is added to values of all the children of node i. Note that when you add value -val to a child of node i, you also add -(-val) to all children of the child of node i and so on. Look an example explanation to understand better how it works.

This tree supports two types of queries:

  * "1 x val" — val is added to the value of node x; 
  * "2 x" — print the current value of node x. 



In order to help Iahub understand the tree better, you must answer m queries of the preceding type.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 200000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000). Each of the next n–1 lines contains two integers vi and ui (1 ≤ vi, ui ≤ n), meaning that there is an edge between nodes vi and ui.

Each of the next m lines contains a query in the format described above. It is guaranteed that the following constraints hold for all queries: 1 ≤ x ≤ n, 1 ≤ val ≤ 1000.

Output

For each query of type two (print the value of node x) you must print the answer to the query on a separate line. The queries must be answered in the order given in the input.

Examples

Input

5 5
1 2 1 1 2
1 2
1 3
2 4
2 5
1 2 3
1 1 2
2 1
2 2
2 4


Output

3
3
0

Note

The values of the nodes are [1, 2, 1, 1, 2] at the beginning.

Then value 3 is added to node 2. It propagates and value -3 is added to it's sons, node 4 and node 5. Then it cannot propagate any more. So the values of the nodes are [1, 5, 1, - 2, - 1].

Then value 2 is added to node 1. It propagates and value -2 is added to it's sons, node 2 and node 3. From node 2 it propagates again, adding value 2 to it's sons, node 4 and node 5. Node 3 has no sons, so it cannot propagate from there. The values of the nodes are [3, 3, - 1, 0, 1].

You can see all the definitions about the tree at the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory)
#include <bits/stdc++.h>
using namespace std;
const long long INF = 2e9 + 33;
const int MX = 2 * 1e5 + 11;
int N, M, k;
struct node {
  int lodd, leven, sum, Nodd;
  node() { lodd = leven = sum = Nodd = 0; }
};
node st[4 * MX];
int lev, t, evenodd;
int ID[MX], St[MX], Ed[MX], arr[MX], LV[MX];
vector<int> G[MX];
void push(int L, int R, int p) {
  int Neven = (R - L + 1) - st[p].Nodd;
  int add = st[p].lodd * st[p].Nodd - st[p].lodd * Neven;
  st[p].sum += add;
  add = st[p].leven * Neven - st[p].leven * st[p].Nodd;
  st[p].sum += add;
  if (L != R) {
    st[p << 1].leven += st[p].leven;
    st[p << 1 | 1].leven += st[p].leven;
    st[p << 1].lodd += st[p].lodd;
    st[p << 1 | 1].lodd += st[p].lodd;
  }
  st[p].leven = st[p].lodd = 0;
}
void up(int L, int R, int p, int i, int j, int val) {
  push(L, R, p);
  if (L > R || L > j || R < i) return;
  if (L >= i && R <= j) {
    if (evenodd == 0)
      st[p].leven = val;
    else
      st[p].lodd = val;
    if (L == R) st[p].Nodd = (LV[ID[R]] % 2) != 0;
    push(L, R, p);
    return;
  }
  int m = (L + R) >> 1;
  up(L, m, p << 1, i, j, val);
  up(m + 1, R, p << 1 | 1, i, j, val);
  st[p].sum = st[p << 1].sum + st[p << 1 | 1].sum;
  st[p].Nodd = st[p << 1].Nodd + st[p << 1 | 1].Nodd;
}
int Q(int L, int R, int p, int i, int j) {
  push(L, R, p);
  if (L > R || L > j || R < i) return 0;
  if (L >= i && R <= j) {
    return st[p].sum;
  }
  int m = (L + R) >> 1;
  return Q(L, m, p << 1, i, j) + Q(m + 1, R, p << 1 | 1, i, j);
}
void dfs(int x, int p) {
  ++LV[x];
  ID[t] = x;
  St[x] = t++;
  if (LV[x] & 1)
    evenodd = 1;
  else
    evenodd = 0;
  up(0, N - 1, 1, St[x], St[x], arr[x]);
  for (int i = 0; i < G[x].size(); i++) {
    int ch = G[x][i];
    if (ch == p) continue;
    LV[ch] = LV[x];
    dfs(ch, x);
  }
  Ed[x] = t - 1;
}
int main() {
  int q;
  scanf("%d%d", &N, &q);
  for (int i = 1; i <= N; i++) scanf("%d", &arr[i]);
  for (int i = 1; i < N; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  dfs(1, -1);
  for (int i = 0; i < q; i++) {
    int ty, x, val;
    scanf("%d%d", &ty, &x);
    if (ty == 1) {
      scanf("%d", &val);
      if (LV[x] & 1)
        evenodd = 1;
      else
        evenodd = 0;
      up(0, N - 1, 1, St[x], Ed[x], val);
    } else {
      cout << Q(0, N - 1, 1, St[x], St[x]) << '\n';
    }
  }
  return 0;
}
