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 int INFint = 2e9;
const long long INF = 2e18;
const int MOD = 1e9 + 7;
struct segtree {
  vector<int> add;
  vector<pair<int, int> > t;
  int sz = 1;
  void push(int v) {
    if (add[v]) {
      t[2 * v].first += add[v] * t[2 * v].second;
      t[2 * v + 1].first += add[v] * t[2 * v + 1].second;
      add[2 * v] += add[v];
      add[2 * v + 1] += add[v];
      add[v] = 0;
    }
  }
  void modify(int l, int r, int lv, int rv, int v, int val) {
    if (l > rv || r < lv) return;
    if (lv >= l && rv <= r) {
      add[v] += val;
      t[v].first += t[v].second * val;
      return;
    }
    int md = (lv + rv) / 2;
    push(v);
    modify(l, r, lv, md, 2 * v, val);
    modify(l, r, md + 1, rv, 2 * v + 1, val);
    t[v].first = t[2 * v].first + t[2 * v + 1].first;
  }
  int sum(int l, int r, int lv, int rv, int v) {
    if (l > rv || r < lv) return 0;
    if (lv >= l && rv <= r) return t[v].first;
    push(v);
    int md = (lv + rv) / 2;
    int res = sum(l, r, lv, md, 2 * v) + sum(l, r, md + 1, rv, 2 * v + 1);
    t[v].first = t[2 * v].first + t[2 * v + 1].first;
    return res;
  }
  segtree(){};
  segtree(int n) {
    t.resize(4 * n);
    add.resize(4 * n);
    while (sz < n) sz *= 2;
    for (int i = sz; i < sz + n; i++) t[i].second = 1;
    for (int i = sz - 1; i > 0; i--)
      t[i].second = t[2 * i].second + t[2 * i + 1].second;
  }
};
vector<vector<int> > g;
vector<int> tin, tout, dist;
int timer;
void dfs(int v, int anc = -1, int len = 0) {
  tin[v] = timer++;
  dist[v] = len;
  for (auto to : g[v]) {
    if (to == anc) continue;
    dfs(to, v, len + 1);
  }
  tout[v] = timer++;
}
int main() {
  ios_base::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  g.resize(n);
  tin.resize(n);
  tout.resize(n);
  dist.resize(n);
  for (auto &x : a) cin >> x;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(0);
  segtree sg(timer);
  for (int i = 0; i < m; i++) {
    int t, v;
    cin >> t >> v;
    v--;
    if (t == 1) {
      int val;
      cin >> val;
      if (dist[v] & 1) {
        sg.modify(tin[v], tout[v], 0, sg.sz - 1, 1, -val);
      } else {
        sg.modify(tin[v], tout[v], 0, sg.sz - 1, 1, val);
      }
    } else {
      if (dist[v] & 1) {
        cout << a[v] - sg.sum(tin[v], tin[v], 0, sg.sz - 1, 1) << '\n';
      } else {
        cout << a[v] + sg.sum(tin[v], tin[v], 0, sg.sz - 1, 1) << '\n';
      }
    }
  }
  fprintf(stderr, "\nTIME = %lf\n", 1.0 * clock() / CLOCKS_PER_SEC);
  ;
  return 0;
}
