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 *a*<sub class="lower-index">*i*</sub>. 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.
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 200000). The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 1000). Each of the next *n*–1 lines contains two integers *v*<sub class="lower-index">*i*</sub> and *u*<sub class="lower-index">*i*</sub> (1 ≤ *v*<sub class="lower-index">*i*</sub>, *u*<sub class="lower-index">*i*</sub> ≤ *n*), meaning that there is an edge between nodes *v*<sub class="lower-index">*i*</sub> and *u*<sub class="lower-index">*i*</sub>.

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.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("arch=skylake")
using namespace std;

struct Fenwick {
    int n;
    vector<int> t;

    Fenwick(int _n): n(_n), t(_n + 1, 0) {}
    void add(int l, int r, int v) {
        for(l++; l <= n; l += l & -l) t[l] += v;
        for(r += 2; r <= n; r += r & -r) t[r] -= v;
    }

    int query(int x) {
        int ans = 0;
        for(x++; x > 0; x -= x & -x) ans += t[x];
        return ans;
    }
};

vector<vector<int>> g;
vector<int> tour_l[2], tour_r[2], tour[2], depth, a;
int timer[2] = {0};

void dfs(int u = 0, int p = -1, int d = 0) {
    depth[u] = d;
    tour_l[d & 1][u] = tour_r[d & 1][u] = timer[d & 1]++;
    tour_l[(d + 1) & 1][u] = timer[(d + 1) & 1];
    tour_r[(d + 1) & 1][u] = timer[(d + 1) & 1] - 1;
    tour[d & 1].push_back(a[u]);
    for(int v: g[u])
        if(v != p) {
            dfs(v, u, d + 1); 
            tour_r[d & 1][u] = max(tour_r[d & 1][u], tour_r[d & 1][v]);
            tour_r[(d + 1) & 1][u] = max(tour_r[(d + 1) & 1][u], tour_r[(d + 1) & 1][v]);
        }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    tour_l[0] = tour_l[1] = tour_r[0] = tour_r[1] = vector<int>(n);
    depth.resize(n);
    g.assign(n, {});
    a.resize(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs();
    Fenwick t[2] = {Fenwick(tour[0].size()), Fenwick(tour[1].size())};
    for(int i = 0; i < m; i++) {
        int type;
        cin >> type;
        if(type == 1) {
            int x, val;
            cin >> x >> val;
            x--;
            t[depth[x] & 1].add(tour_l[depth[x] & 1][x], tour_r[depth[x] & 1][x], val);
            t[(depth[x] + 1) & 1].add(tour_l[(depth[x] + 1) & 1][x], tour_r[(depth[x] + 1) & 1][x], -val);
        } else {
            int x;
            cin >> x;
            x--;
            cout << t[depth[x] & 1].query(tour_l[depth[x] & 1][x]) + a[x] << "\n";
        }
    }
}