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.List;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Locale;
import java.util.TimeZone;

public class A {

	public static void main(String[] args) {
		Locale.setDefault(Locale.US);
		InputStream inputstream = System.in;
		OutputStream outputstream = System.out;
		FastReader in = new FastReader(inputstream);
		PrintWriter out = new PrintWriter(outputstream);
		TaskA solver = new TaskA();
		// int testcase = in.ni();
		for (int i = 0; i < 1; i++)
			solver.solve(i, in, out);
		out.close();

	}

}

class Fenwick {

	int N;
	int fen[];

	public Fenwick(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;
	}

}

class EulerTour {

	int discover[];
	int begin[];
	int end[];
	int level[];
	int parent[];
	int indexes[];

	public EulerTour(ArrayList<Integer> 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 visit[] = new boolean[n];
		stack[pos++] = 0;
		parent[0] = -1;
		level[0] = 0;
		int clock = 0;
		int count = 0;

		outer: while (pos != 0) {
			int cur = stack[pos - 1];
			if (!visit[cur]) {
				begin[cur] = clock++;
				discover[count++] = cur;
				visit[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 int[] getBegin() {
		return begin;
	}

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

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

}

class TaskA {

	public void solve(int testnumber, FastReader in, PrintWriter out) {
		
		int n = in.ni();
		int query = in.ni();

		int a[] = in.iArr(n);

		ArrayList<Integer> G[] = new ArrayList[n];

		for (int i = 0; i < n; i++) {
			G[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < n - 1; i++) {
			int x = in.ni() - 1;
			int y = in.ni() - 1;
			G[x].add(y);
			G[y].add(x);
		}
		EulerTour euler = new EulerTour(G);
		int[] begin = euler.getBegin();
		int[] level = euler.getLevel();
		int[] end = euler.getEnd();

		Fenwick fteven = new Fenwick(n + 1);
		Fenwick ftodd = new Fenwick(n + 1);
		

		while (query > 0) {

			int type = in.ni();

			if (type == 1) {
				int node = in.ni() - 1;
				int val = in.ni();
				if (level[node] % 2 == 0) {
					fteven.update(begin[node], val);
					ftodd.update(begin[node], -val);
					fteven.update(end[node] + 1, -val);
					ftodd.update(end[node] + 1, val);
				} else {
					fteven.update(begin[node], -val);
					ftodd.update(begin[node], val);
					fteven.update(end[node] + 1, val);
					ftodd.update(end[node] + 1, -val);
				}
			} else {
				int node = in.ni() - 1 ;
				long res = a[node];
				if (level[node] % 2 == 0) {
					res += fteven.getSum(begin[node]);
				} else {
					res += ftodd.getSum(begin[node]);
				}

				out.println(res);
			}

			query--;

		}

	}
}

class FastReader {
	public InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

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

	public FastReader() {

	}

	public 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 ni() {
		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 String ns() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	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 int[] iArr(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = ni();
		}
		return a;
	}

	public String next() {
		return ns();
	}

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

}