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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Pradyumn Agrawal coderbond007
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int n = in.nextInt();
            int Q = in.nextInt();
            int[] a = in.nextIntArray(n);
            List<Integer>[] g = CollectionUtils.generateListArray(n);
            for (int i = 0; i < n - 1; i++) {
                int u = in.nextInt() - 1;
                int v = in.nextInt() - 1;
                g[u].add(v);
                g[v].add(u);
            }
            EulerTour eulerTour = new EulerTour(g);
            int[] begin = eulerTour.getBegin();
            int[] end = eulerTour.getEnd();
            int[] level = eulerTour.getLevel();
            FenwickTree ftEven = new FenwickTree(n + 1);
            FenwickTree ftOdd = new FenwickTree(n + 1);
            for (int q = 0; q < Q; q++) {
                int type = in.nextInt();
                if (type == 1) {
                    int x = in.nextInt() - 1;
                    int val = in.nextInt();
                    if (level[x] % 2 == 0) {
                        ftEven.update(begin[x], val);
                        ftOdd.update(begin[x], -val);
                        ftEven.update(end[x] + 1, -val);
                        ftOdd.update(end[x] + 1, val);
                    } else {
                        ftEven.update(begin[x], -val);
                        ftOdd.update(begin[x], val);
                        ftEven.update(end[x] + 1, val);
                        ftOdd.update(end[x] + 1, -val);
                    }
                } else {
                    int v = in.nextInt() - 1;
                    int res = a[v];
                    if (level[v] % 2 == 0) {
                        res += ftEven.getSum(begin[v]);
                    } else {
                        res += ftOdd.getSum(begin[v]);
                    }
                    out.println(res);
                }
            }
        }

    }

    static class EulerTour {
        public int[] discover;
        public int[] begin;
        public int[] end;
        public int[] level;
        public int[] parent;
        public int[] indexes;

        public EulerTour(List<Edge>[] g) {
            int n = g.length;
            int[] stack = new int[n];
            int pos = 0;
            discover = new int[n];
            begin = new int[n];
            end = new int[n];
            level = new int[n];
            parent = new int[n];
            indexes = new int[n];
            boolean[] visited = new boolean[n];
            stack[pos++] = 0;
            level[0] = 0;
            parent[0] = -1;
            int clock = 0;
            int count = 0;
            outer:
            while (pos != 0) {
                int cur = stack[pos - 1];
                if (!visited[cur]) {
                    begin[cur] = clock++;
                    discover[count++] = cur;
                    visited[cur] = true;
                }
                while (indexes[cur] < g[cur].size()) {
                    int next = g[cur].get(indexes[cur]++).to;
                    if (parent[cur] != next) {
                        parent[next] = cur;
                        level[next] = level[cur] + 1;
                        stack[pos++] = next;
                        continue outer;
                    }
                }
                pos--;
                if (indexes[cur] == g[cur].size()) end[cur] = clock - 1;
            }
        }

        public EulerTour(List<Integer>[] g, Object... objects) {
            int n = g.length;
            int[] stack = new int[n];
            int pos = 0;
            discover = new int[n];
            begin = new int[n];
            end = new int[n];
            level = new int[n];
            parent = new int[n];
            indexes = new int[n];
            boolean[] visited = new boolean[n];
            stack[pos++] = 0;
            level[0] = 0;
            parent[0] = -1;
            int clock = 0;
            int count = 0;
            outer:
            while (pos != 0) {
                int cur = stack[pos - 1];
                if (!visited[cur]) {
                    begin[cur] = clock++;
                    discover[count++] = cur;
                    visited[cur] = true;
                }
                while (indexes[cur] < g[cur].size()) {
                    int next = g[cur].get(indexes[cur]++);
                    if (parent[cur] != next) {
                        parent[next] = cur;
                        level[next] = level[cur] + 1;
                        stack[pos++] = next;
                        continue outer;
                    }
                }
                pos--;
                if (indexes[cur] == g[cur].size()) end[cur] = clock - 1;
            }
        }

        public EulerTour(int[][][] g) {
            int n = g.length;
            int[] stack = new int[n];
            int pos = 0;
            discover = new int[n];
            begin = new int[n];
            end = new int[n];
            level = new int[n];
            parent = new int[n];
            indexes = new int[n];
            boolean[] visited = new boolean[n];
            stack[pos++] = 0;
            level[0] = 0;
            parent[0] = -1;
            int clock = 0;
            int count = 0;
            outer:
            while (pos != 0) {
                int cur = stack[pos - 1];
                if (!visited[cur]) {
                    begin[cur] = clock++;
                    discover[count++] = cur;
                    visited[cur] = true;
                }
                while (indexes[cur] < g[cur].length) {
                    int next = g[cur][indexes[cur]++][0];
                    if (parent[cur] != next) {
                        parent[next] = cur;
                        level[next] = level[cur] + 1;
                        stack[pos++] = next;
                        continue outer;
                    }
                }
                pos--;
                if (indexes[cur] == g[cur].length) end[cur] = clock - 1;
            }
        }

        public EulerTour(int[][] g) {
            int n = g.length;
            int[] stack = new int[n];
            int pos = 0;
            discover = new int[n];
            begin = new int[n];
            end = new int[n];
            level = new int[n];
            parent = new int[n];
            indexes = new int[n];
            boolean[] visited = new boolean[n];
            stack[pos++] = 0;
            level[0] = 0;
            parent[0] = -1;
            int clock = 0;
            int count = 0;
            outer:
            while (pos != 0) {
                int cur = stack[pos - 1];
                if (!visited[cur]) {
                    begin[cur] = clock++;
                    discover[count++] = cur;
                    visited[cur] = true;
                }
                while (indexes[cur] < g[cur].length) {
                    int next = g[cur][indexes[cur]++];
                    if (parent[cur] != next) {
                        parent[next] = cur;
                        level[next] = level[cur] + 1;
                        stack[pos++] = next;
                        continue outer;
                    }
                }
                pos--;
                if (indexes[cur] == g[cur].length) end[cur] = clock - 1;
            }
        }

        public int[] getBegin() {
            return begin;
        }

        public int[] getEnd() {
            return end;
        }

        public int[] getLevel() {
            return level;
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar;
        private int pnumChars;
        private FastReader.SpaceCharFilter filter;

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

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

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

        public int[] nextIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class FenwickTree {
        public int[] fen;
        public int N;

        public FenwickTree(int[] a) {
            N = a.length;
            fen = new int[N + 1];

            for (int i = 0; i < N; i++) {
                for (int x = i + 1; x <= N; x += x & (-x)) {
                    fen[x] += a[i];
                }
            }
        }

        public FenwickTree(int n) {
            N = n;
            fen = new int[N + 1];
        }

        public void update(int ind, int val) {
            if (val == 0) return;
            for (int x = ind + 1; x <= N; x += x & (-x)) {
                fen[x] += val;
            }
        }

        public long getSum(int ind) {
            long sum = 0;
            for (int x = ind + 1; x > 0; x -= x & (-x)) {
                sum += fen[x];
            }
            return sum;
        }

    }

    static class Edge implements Comparable<Edge> {
        public int from;
        public int to;
        public long weight = Long.MIN_VALUE;
        public long cost = Long.MIN_VALUE;
        public long capacity = Long.MIN_VALUE;

        public Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }

        public Edge(int from, int to, long weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public Edge(int from, int to, long capacity, long cost) {
            this.from = from;
            this.to = to;
            this.capacity = capacity;
            this.cost = cost;
        }


        public int compareTo(Edge edge) {
            if (this.from != edge.from) return Integer.compare(this.from, edge.from);
            if (this.to != edge.to) return Integer.compare(this.to, edge.to);
            if (this.weight != edge.weight) return Long.compare(this.weight, edge.weight);
            if (this.cost != edge.cost) return Long.compare(this.cost, edge.cost);
            return 0;
        }


        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Edge edge = (Edge) o;

            if (this.from != edge.from) return false;
            if (this.to != edge.to) return false;
            if (this.weight != edge.weight) return false;
            if (this.cost != edge.cost) return false;
            if (this.capacity != edge.capacity) return false;
            return true;
        }


        public int hashCode() {
            long result = from != 0 ? new Integer(from).hashCode() : 0;
            result = (31 * result) + ((to != 0) ? new Integer(to).hashCode() : 0);
            result = (31 * result) + ((weight != 0) ? new Long(weight).hashCode() : 0);
            result = (31 * result) + ((cost != 0) ? new Long(cost).hashCode() : 0);
            result = (31 * result) + ((capacity != 0) ? new Long(capacity).hashCode() : 0);
            return (int) result;
        }


        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append("from -> " + from);
            stringBuilder.append(" to -> " + to);
            if (weight != Long.MIN_VALUE) stringBuilder.append(" weight -> " + weight);
            if (cost != Long.MIN_VALUE) stringBuilder.append(" cost -> " + cost);
            if (capacity != Long.MIN_VALUE) stringBuilder.append(" capacity -> " + capacity);
            return stringBuilder.toString();
        }

    }

    static class CollectionUtils {
        public static <E> List<E>[] generateListArray(int size) {
            return Stream.generate(ArrayList::new).limit(size).toArray(List[]::new);
        }

    }
}