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)
/*
Keep solving problems. 
*/
import java.util.*;
import java.io.*;

public class CFA {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    int[] dx = {1, 2, 1, 1};
    int[] dy = {0, 0, -1, 1};


    class BIT {
        private long[] fen;
        private int n;
        BIT(int n) {
            this.n = n;
            fen = new long[1 + n];
        }
        void update(int p, long val){ //add val to tree node at p and all its parent, p is 0-based
            p++;
            for(int i = p; i <= n; i += i & -i)
                fen[i] += val;
        }
        long sum(int p){ //get sum between [0, p], p is 0-based
            long res = 0;
            p++;
            for(int i = p; i > 0; i -= i & -i)
                res += fen[i];
            return res;
        }
        void updateRange(int start, int end, long val) {
            update(start, val);
            update(end + 1, -val);
        }
//
//        public static void main(String[] args) {
//            BIT ins = new BIT();
//            int[] arr = {1, 2, 3, 4, 5};
//            ins.initPara(arr);
//            int n = arr.length;
//            for(int i = 0; i < n; i++) {
//                ins.update(i, arr[i]);
//            }
//            System.out.println(ins.sum(3));
//        }
    }

    int INDEX = 0;
    int n;
    List<List<Integer>> graph;
    int[] startIndex;
    int[] endIndex;
    int[] parity;
    void solve() throws IOException {
        INDEX = 0;
        n = nextInt();
        int m = nextInt();
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] arr = nextIntArr(n);
        for (int i = 0; i < n - 1; i++) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        startIndex = new int[n];
        endIndex = new int[n];
        parity = new int[n];
        dfs(0, 0, -1);

        BIT even = new BIT(n);
        BIT odd = new BIT(n);

        for (int i = 0; i < n; i++) {
            if (parity[i] == 0) {
                even.updateRange(startIndex[i], startIndex[i], arr[i]);
            }
            else {
                odd.updateRange(startIndex[i], startIndex[i], arr[i]);
            }
        }

        List<Long> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int q = nextInt();
            if (q == 1) {
                int x = nextInt() - 1;
                int val = nextInt();
                if (parity[x] == 0) {
                    even.updateRange(startIndex[x], endIndex[x], val);
                    odd.updateRange(startIndex[x], endIndex[x], -val);
                }
                else {
                    even.updateRange(startIndex[x], endIndex[x], -val);
                    odd.updateRange(startIndex[x], endIndex[x], val);
                }
            }
            else {
                int x = nextInt() - 1;
                if (parity[x] == 0) {
                    res.add(even.sum(startIndex[x]));
                }
                else {
                    res.add(odd.sum(startIndex[x]));
                }
            }
        }

        for (int i = 0; i < res.size(); i++) {
            outln(res.get(i));
        }
    }

    void dfs(int nodeIndex, int par, int parent) {
        startIndex[nodeIndex] = INDEX;
        INDEX++;
        parity[nodeIndex] = par;
        for (int nxt : graph.get(nodeIndex)) {
            if (nxt != parent) {
                dfs(nxt, 1 - par, nodeIndex);
            }
        }

        endIndex[nodeIndex] = INDEX - 1;
    }


    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }

    long gcd(long a, long b) {
        while(a != 0 && b != 0) {
            long c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }

    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public CFA() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFA();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}

