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>
#pragma GCC optimize("O3")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int grand(int x) { return uniform_int_distribution<int>(0, x - 1)(rng); }
string s = "";
long long arr[1000005] = {0};
long long brr[1000005] = {0};
long long orr[1000005] = {0};
long long son[1000005] = {0};
long long par[1000005] = {0};
long long sza[1000005] = {0};
long long sze[1000005] = {0};
long long szo[1000005] = {0};
long long pso[1000005] = {0};
long long pse[1000005] = {0};
long long bitve[1000005] = {0};
long long bitvo[1000005] = {0};
vector<long long> v;
vector<long long> ve, vo;
vector<long long> g[1000005], go[1000005], ge[1000005];
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  if (a == 0) return b;
  return gcd(b, a % b);
}
void dfs(long long x, long long y) {
  arr[x] = 1;
  orr[x] = y;
  long long z = 0;
  for (int i : g[x]) {
    if (arr[i] == 1) continue;
    if (z == 0) {
      son[x] = i;
      z = 1;
    }
    par[i] = x;
    dfs(i, y + 1);
  }
}
void dfso(long long x) {
  arr[x] = 1;
  pso[x] = vo.size();
  vo.push_back(brr[x]);
  for (int i : g[x]) {
    if (i == par[x]) continue;
    for (int j : g[i]) {
      if (arr[j] == 1) continue;
      go[x].push_back(j);
      go[j].push_back(x);
      dfso(j);
    }
  }
}
void dfse(long long x) {
  arr[x] = 1;
  pse[x] = ve.size();
  ve.push_back(brr[x]);
  for (int i : g[x]) {
    if (i == par[x]) continue;
    for (int j : g[i]) {
      if (arr[j] == 1) continue;
      ge[x].push_back(j);
      ge[j].push_back(x);
      dfse(j);
    }
  }
}
long long gszo(long long x) {
  arr[x] = 1;
  long long ans = 1;
  for (int i : go[x]) {
    if (arr[i] == 1) continue;
    ans += gszo(i);
  }
  szo[x] = ans;
  return ans;
}
long long gsze(long long x) {
  arr[x] = 1;
  long long ans = 1;
  for (int i : ge[x]) {
    if (arr[i] == 1) continue;
    ans += gsze(i);
  }
  sze[x] = ans;
  return ans;
}
void updo(long long x, long long val) {
  for (int i = x + 1; i < 1000005; i += i & (-i)) {
    bitvo[i] += val;
  }
}
long long getsumo(long long x) {
  long long sum = 0;
  for (int i = x + 1; i > 0; i -= i & (-i)) {
    sum += bitvo[i];
  }
  return sum;
}
void upde(long long x, long long val) {
  for (int i = x + 1; i < 1000005; i += i & (-i)) {
    bitve[i] += val;
  }
}
long long getsume(long long x) {
  long long sum = 0;
  for (int i = x + 1; i > 0; i -= i & (-i)) {
    sum += bitve[i];
  }
  return sum;
}
int main() {
  ios ::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n = 0, m = 0, k = 0, q = 0, ans = 0;
  long long x = 0, y = 0, t = 0, sum = 0, sz = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> brr[i];
  }
  for (int i = 0; i < n - 1; i++) {
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  g[0].push_back(1);
  g[1].push_back(0);
  vo.push_back(0);
  dfs(0, 0);
  fill(arr, arr + 1000005, 0);
  dfso(1);
  fill(arr, arr + 1000005, 0);
  dfse(0);
  fill(arr, arr + 1000005, 0);
  gszo(1);
  fill(arr, arr + 1000005, 0);
  gsze(0);
  long long val;
  for (int i = 1; i < vo.size(); i++) {
    updo(i, vo[i] - vo[i - 1]);
  }
  for (int i = 1; i < ve.size(); i++) {
    upde(i, ve[i] - ve[i - 1]);
  }
  for (int i = 0; i <= n; i++) {
    if (orr[i] % 2 == 1) {
      for (int j : g[i]) {
        if (j == par[i]) continue;
        sza[i] += sze[j];
      }
    } else {
      for (int j : g[i]) {
        if (j == par[i]) continue;
        sza[i] += szo[j];
      }
    }
  }
  while (m--) {
    cin >> q;
    if (q == 1) {
      cin >> x >> val;
      if (orr[x] % 2 == 1) {
        updo(pso[x], val);
        updo(pso[x] + szo[x], -val);
        if (g[x].size() != 0) upde(pse[son[x]], -val);
        if (g[x].size() != 0) upde(pse[son[x]] + sza[x], val);
      } else {
        upde(pse[x], val);
        upde(pse[x] + sze[x], -val);
        if (g[x].size() != 0) updo(pso[son[x]], -val);
        if (g[x].size() != 0) updo(pso[son[x]] + sza[x], val);
      }
    } else {
      cin >> x;
      if (orr[x] % 2 == 1) {
        cout << getsumo(pso[x]) << endl;
      } else {
        cout << getsume(pse[x]) << endl;
      }
    }
  }
  return 0;
}
