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 double PI = acos(-1);
const long long MOD = 1000000000 + 7;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long add(long long a, long long b, long long m = MOD) {
  return (a % m + b % m + 2 * m) % m;
}
long long mul(long long a, long long b, long long m = MOD) {
  return ((a % m + m) * (b % m + m)) % m;
}
long long pow_mod(long long a, long long b, long long m = MOD) {
  long long res = 1LL;
  a = a % m;
  while (b) {
    if (b & 1) res = mul(res, a, m);
    b >>= 1;
    a = mul(a, a, m);
  }
  return res;
}
long long fastexp(long long a, long long b) {
  long long res = 1LL;
  while (b) {
    if (b & 1) res = res * a;
    b >>= 1;
    a *= a;
  }
  return res;
}
int gcdExtendido(int a, int b, int *x, int *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }
  int x1, y1;
  int gcd = gcdExtendido(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
int modInverso(int a, int m) {
  int x, y;
  int g = gcdExtendido(a, m, &x, &y);
  if (g != 1)
    return -1;
  else
    return (x % m + m) % m;
}
class FenwickTree {
  vector<int> f;
  int n;

 public:
  FenwickTree(){};
  FenwickTree(int n) {
    this->n = n;
    f.assign(n + 1, 0);
  }
  int getSum(int i) {
    int ans = 0;
    i++;
    while (i > 0) {
      ans += f[i];
      i &= i - 1;
    }
    return ans;
  }
  void update(int i, int val) {
    i++;
    while (i <= n) {
      f[i] += val;
      i += (i & (-i));
    }
  }
  int query(int L, int R) { return getSum(R) - getSum(L - 1); }
};
struct Query {
  int op;
  int l;
  int r;
  Query(){};
  Query(int _op, int _l, int _r = 0) {
    op = _op;
    l = _l;
    r = _r;
  }
};
const int N = 200000 + 5;
int n, m;
int c[N];
int L[N];
int R[N];
int T;
vector<int> G[N];
vector<int> Nodes[N];
int level[N];
int pos_in_parity[N];
FenwickTree F[3];
void DFS(int u, int p = 0) {
  level[u] = level[p] ^ 1;
  Nodes[level[u]].push_back(u);
  L[u] = T++;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (v != p) {
      DFS(v, u);
    }
  }
  R[u] = T - 1;
}
void preprocess() {
  level[0] = 1;
  DFS(1);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < Nodes[i].size(); j++) {
      int u = Nodes[i][j];
      pos_in_parity[u] = j;
    }
  }
  for (int i = 0; i < 2; i++) {
    F[i] = FenwickTree(Nodes[i].size() + 5);
  }
}
int query(int u) {
  int pos = pos_in_parity[u];
  return F[level[u]].query(0, pos);
}
void updateUtil(int par, int l, int r, int val) {
  int lo = 0, hi = Nodes[par].size() - 1;
  while (lo < hi) {
    int mi = lo + (hi - lo) / 2;
    if (L[Nodes[par][mi]] < l)
      lo = mi + 1;
    else
      hi = mi;
  }
  if (L[Nodes[par][lo]] < l or L[Nodes[par][lo]] > r) return;
  F[par].update(lo, val);
  hi = Nodes[par].size() - 1;
  while (lo < hi) {
    int mi = lo + (hi - lo + 1) / 2;
    if (L[Nodes[par][mi]] <= r)
      lo = mi;
    else
      hi = mi - 1;
  }
  F[par].update(lo + 1, -val);
}
void update(int u, int val) {
  if (Nodes[level[u]].size()) updateUtil(level[u], L[u], R[u], val);
  if (Nodes[level[u] ^ 1].size()) updateUtil(level[u] ^ 1, L[u], R[u], -val);
}
int main() {
  scanf("%d %d", &(n), &(m));
  for (int i = 1; i <= n; i++) {
    scanf("%d", &(c[i]));
  }
  int a, b;
  for (int i = 1; i < n; i++) {
    scanf("%d %d", &(a), &(b));
    G[a].push_back(b);
    G[b].push_back(a);
  }
  preprocess();
  int op;
  int t1 = 0, t2 = 0;
  for (int i = 0; i < m; i++) {
    scanf("%d", &(op));
    if (op == 1) {
      scanf("%d %d", &(a), &(b));
      update(a, b);
    } else {
      scanf("%d", &(a));
      printf("%d\n", c[a] + query(a));
    }
  }
  return 0;
}
