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)

import java.awt.Point;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.InputMismatchException;

public class E {
    static ArrayDeque<Integer>[] E;
    static int[] Odd;
    static int[] Even;
    static boolean[] isEven;
    static int oddCount = 1, evenCount = 1;
    static Point[] evenRange;
    static Point[] oddRange;
    static BIT oddL, evenL;
    static int[] M;

    public static void update(int st, int end, int v, BIT T) {
        if (st > end)
            return;
        T.update(st, v);
        if (end + 1 < T.size())
            T.update(end + 1, -v);
    }

    public static void dfs(int x, int p, int parity) {
        evenRange[x] = new Point(evenCount, -1);
        oddRange[x] = new Point(oddCount, -1);
        if (parity == 0) {
            isEven[x] = true;
            Even[evenCount++] = x;
        } else {
            Odd[oddCount++] = x;
        }
        for (int y : E[x])
            if (y != p)
                dfs(y, x, parity ^ 1);
        oddRange[x].y = oddCount - 1;
        evenRange[x].y = evenCount - 1;
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.readInt();
        int m = in.readInt();
        int[] A = new int[n];
        E = new ArrayDeque[n];
        for (int i = 0; i < n; i++) {
            A[i] = in.readInt();
            E[i] = new ArrayDeque<Integer>();
        }
        for (int i = 1; i < n; i++) {
            int x = in.readInt() - 1;
            int y = in.readInt() - 1;
            E[x].add(y);
            E[y].add(x);
        }
        Odd = new int[n + 1];
        Even = new int[n + 1];
        evenRange = new Point[n];
        oddRange = new Point[n];
        isEven = new boolean[n];
        dfs(0, -1, 0);
        M = new int[n];
        oddL = new BIT(oddCount);
        evenL = new BIT(evenCount);
        int last = 0;
        for (int i = 1; i < oddCount; i++) {
            M[Odd[i]] = i;
            oddL.update(i, A[Odd[i]] - last);
            last = A[Odd[i]];
        }
        last = 0;
        for (int i = 1; i < evenCount; i++) {
            M[Even[i]] = i;
            evenL.update(i, A[Even[i]] - last);
            last = A[Even[i]];
        }

        for (int i = 0; i < m; i++) {
            int t = in.readInt();
            int x = in.readInt() - 1;
            if (t == 1) {
                int v = in.readInt();
                if (isEven[x]) {
                    update(evenRange[x].x, evenRange[x].y, v, evenL);
                    update(oddRange[x].x, oddRange[x].y, -v, oddL);
                } else {
                    update(evenRange[x].x, evenRange[x].y, -v, evenL);
                    update(oddRange[x].x, oddRange[x].y, v, oddL);
                }
            } else {
                if (isEven[x])
                    out.println(evenL.read(M[x]));
                else
                    out.println(oddL.read(M[x]));
            }
        }
        out.flush();
        out.close();
    }
}

class BIT {
    int[] tree;

    public BIT(int n) {
        tree = new int[n];
    }

    public int read(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }

    public void update(int idx, int val) {
        while (idx < tree.length) {
            tree[idx] += val;
            idx += (idx & -idx);
        }
    }

    public int size() {
        return tree.length;
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1000];
    private int curChar, numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    private int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String readString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuffer buf = new StringBuffer();
        int c = read();
        while (c != '\n' && c != -1) {
            buf.appendCodePoint(c);
            c = read();
        }
        return buf.toString();
    }

    public String readLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String readLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines)
            return readLine();
        else
            return readLine0();
    }

    public char readCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }
}