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 mod = 1000000007;
const long long inf = 1LL << 62;
const long long mx = 100005;
const double eps = 1e-10;
long long dx[10] = {1, 0, -1, 0};
long long dy[10] = {0, -1, 0, 1};
long long power(long long a, long long b) {
  if (b == 0) return 1;
  long long x = power(a, b / 2);
  x = x * x;
  if (b % 2) x = x * a;
  return x;
}
long long bigmod(long long a, long long b) {
  if (b == 0) return 1;
  long long x = bigmod(a, b / 2) % mod;
  x = (x * x) % mod;
  if (b % 2) x = (x * a) % mod;
  return x;
}
long long Set(long long N, long long pos) { return N = N | (1LL << pos); }
long long reset(long long N, long long pos) { return N = N & ~(1LL << pos); }
bool check(long long N, long long pos) { return (bool)(N & (1LL << pos)); }
vector<long long> graph[2 * mx];
long long arr[2 * mx], dis[2 * mx];
pair<long long, long long> pr[2 * mx];
long long mm[2 * mx], cnt;
void dfs(long long s, long long par, long long d) {
  mm[++cnt] = s;
  pr[s].first = cnt;
  dis[s] = d % 2;
  for (long long i = 0; i < (long long)(graph[s]).size(); i++) {
    long long v = graph[s][i];
    if (v == par) continue;
    dfs(v, s, dis[s] + 1);
  }
  pr[s].second = cnt;
}
long long odd[8 * mx], even[8 * mx];
void propagate(long long at, long long L, long long R) {
  long long mid = (L + R) / 2;
  long long left_at = 2 * at, right_at = 2 * at + 1;
  long long left_L = L, left_R = mid, right_L = mid + 1, right_R = R;
  odd[left_at] += odd[at];
  odd[right_at] += odd[at];
  even[left_at] += even[at];
  even[right_at] += even[at];
  odd[at] = even[at] = 0;
}
void build(long long at, long long L, long long R) {
  if (L == R) {
    odd[at] = even[at] = 0;
    return;
  }
  long long mid = (L + R) / 2;
  build(2 * at, L, mid);
  build(2 * at + 1, mid + 1, R);
}
void update(long long at, long long L, long long R, long long l, long long r,
            long long val, long long d) {
  if (r < L || l > R) return;
  if (l <= L && r >= R) {
    if (d == 0) {
      even[at] += val;
      odd[at] -= val;
    } else {
      even[at] -= val;
      odd[at] += val;
    }
    return;
  }
  if (odd[at]) propagate(at, L, R);
  long long mid = (L + R) / 2;
  update(2 * at, L, mid, l, r, val, d);
  update(2 * at + 1, mid + 1, R, l, r, val, d);
}
long long query(long long at, long long L, long long R, long long l,
                long long r, long long d) {
  if (r < L || l > R) return 0;
  if (l <= L && r >= R) {
    if (d)
      return odd[at];
    else
      return even[at];
  }
  if (odd[at]) propagate(at, L, R);
  long long mid = (L + R) / 2;
  long long p = query(2 * at, L, mid, l, r, d);
  long long q = query(2 * at + 1, mid + 1, R, l, r, d);
  return p + q;
}
int main() {
  long long tst, a, b, c, k, n, m, res = 0, ans = 0, t = 0;
  scanf("%lld", &n), scanf("%lld", &m);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &arr[i]);
  }
  for (long long i = 1; i < n; i++) {
    scanf("%lld", &a), scanf("%lld", &b);
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  dfs(1, 0, 0);
  build(1, 1, cnt);
  for (long long i = 1; i <= m; i++) {
    scanf("%lld", &a);
    if (a == 1) {
      scanf("%lld", &b), scanf("%lld", &c);
      update(1, 1, cnt, pr[b].first, pr[b].second, c, dis[b]);
    } else {
      scanf("%lld", &b);
      res = query(1, 1, cnt, pr[b].first, pr[b].first, dis[b]);
      cout << res + arr[b] << "\n";
    }
  }
  return 0;
}
