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;
int n, m;
int a[200005];
vector<int> adj[200005];
int L[200005], P[200005], sz[200005], sc[200005];
bool visited[200005];
int chainNo = 0, ptr = 0;
int chainIdx[200005], chainPos[200005], chainSize[200005], chainHead[200005];
int baseArr[200005], posBase[200005];
int st[4 * 200005];
void init() {
  memset(visited, false, sizeof(visited));
  for (int i = 0; i < 200005; i++) {
    chainIdx[i] = chainPos[i] = chainHead[i] = -1;
    chainSize[i] = 0;
  }
  for (int i = 0; i < 4 * 200005; i++) {
    st[i] = 0;
  }
  return;
}
void updateTree(int x, int val, int l = 0, int r = n - 1, int idx = 0) {
  if (l == r) {
    st[idx] += val;
    return;
  }
  int mid = l + (r - l) / 2;
  if (x <= mid)
    updateTree(x, val, l, mid, 2 * idx + 1);
  else
    updateTree(x, val, mid + 1, r, 2 * idx + 2);
  st[idx] = st[2 * idx + 1] + st[2 * idx + 2];
  return;
}
int queryTree(int x, int y, int l = 0, int r = n - 1, int idx = 0) {
  if (y < l || r < x)
    return 0;
  else if (x <= l && r <= y) {
    return st[idx];
  }
  int mid = l + (r - l) / 2;
  return queryTree(x, y, l, mid, 2 * idx + 1) +
         queryTree(x, y, mid + 1, r, 2 * idx + 2);
}
void dfs(int src) {
  visited[src] = true;
  sz[src] = 1;
  sc[src] = -1;
  int maxm = 0;
  for (auto it : adj[src]) {
    if (!visited[it]) {
      P[it] = src;
      L[it] = L[src] + 1;
      dfs(it);
      sz[src] += sz[it];
      if (sz[it] > maxm) {
        sc[src] = it;
        maxm = sz[it];
      }
    }
  }
  return;
}
void hld(int cur) {
  visited[cur] = true;
  if (chainHead[chainNo] == -1) chainHead[chainNo] = cur;
  chainIdx[cur] = chainNo;
  chainPos[cur] = chainSize[chainNo];
  baseArr[ptr] = 0;
  posBase[cur] = ptr;
  ptr++;
  chainSize[chainNo]++;
  if (sc[cur] != -1) {
    hld(sc[cur]);
  }
  for (auto it : adj[cur]) {
    if (!visited[it] && it != sc[cur]) {
      chainNo++;
      hld(it);
    }
  }
  return;
}
int query_up(int l, int u) {
  int uchain = chainIdx[u];
  bool ltype = L[l] % 2;
  int ans = 0;
  while (1) {
    int lchain = chainIdx[l];
    if (uchain == lchain) {
      ans += queryTree(posBase[u], posBase[l]);
      break;
    }
    int h = chainHead[chainIdx[l]];
    ans += queryTree(posBase[h], posBase[l]);
    l = P[h];
  }
  if (ltype) ans = -ans;
  return ans;
}
void update(int x, int val) {
  int idx = posBase[x];
  if (L[x] % 2 == 0)
    updateTree(idx, val);
  else
    updateTree(idx, -val);
  return;
}
int query(int x) {
  int ans = query_up(x, 0);
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  init();
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int u, v;
  for (int i = 0; i < n - 1; i++) {
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  P[0] = -1;
  L[0] = 0;
  dfs(0);
  memset(visited, false, sizeof(visited));
  hld(0);
  int t;
  int x, val;
  while (m--) {
    cin >> t;
    if (t == 1) {
      cin >> x >> val;
      x--;
      update(x, val);
    } else if (t == 2) {
      cin >> x;
      x--;
      int ans = query(x);
      ans += a[x];
      cout << ans << "\n";
    }
  }
  return 0;
}
