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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	static int n;
	static ArrayList<Integer> tree [];
	static int [] arr, start, end, dfs_tree, even, odd, depth;
	static TreeMap<Integer, Integer> even_start_map = new TreeMap<>(), odd_start_map = new TreeMap<>();
	static TreeMap<Integer, Integer> even_end_map = new TreeMap<>(), odd_end_map = new TreeMap<>();
	// start[i] the time of node i, end[i] is the time of the last node in the subtree
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		n = sc.nextInt();
		int q = sc.nextInt();
		arr = new int[n];
		start = new int[n];
		end = new int[n];
		even = new int[n];
		odd = new int[n];
		dfs_tree = new int[n];
		tree = new ArrayList[n];
		depth = new int[n];
		for (int i = 0; i < n; i++)
			tree[i] = new ArrayList<>();
		for (int i = 0; i < n; i++)
			arr[i] = sc.nextInt();
		
		for (int i = 0; i < n - 1; i++) {
			int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
			tree[u].add(v);
			tree[v].add(u);
		}
		
		dfs(0, -1);
		ST [] sts = new ST[2];
		sts[0] = new ST(even);
		sts[1] = new ST(odd);
		
//		System.out.println("start = " + Arrays.toString(start));
//		System.out.println("end = " + Arrays.toString(end));
//		System.out.println("dfs_Tree = " + Arrays.toString(dfs_tree));
//		System.out.println("even = " + Arrays.toString(even));
//		System.out.println("odd = " + Arrays.toString(odd));
//		
//		System.out.println("even_start_map = " + even_start_map);
//		System.out.println("even_end_map = " + even_end_map);
//		System.out.println("odd_start_map = " + odd_start_map);
//		System.out.println("odd_end_map = " + odd_end_map);
		
		
		while(q-->0) {
			int op = sc.nextInt();
			int x = sc.nextInt() - 1;
			if (op == 1) {
				int val = sc.nextInt();
				if(depth[x] == 0) {
					sts[0].update(1, 0, n - 1, even_start_map.get(start[x]), even_end_map.floorEntry(end[x]).getValue(), val);
					Integer oddStart = odd_start_map.higherKey(start[x]);
					if (oddStart != null && oddStart <= end[x]) {
						sts[1].update(1, 0, n - 1, odd_start_map.get(oddStart), odd_end_map.floorEntry(end[x]).getValue(), -val);
					}
				}
				else {
					sts[1].update(1, 0, n - 1, odd_start_map.get(start[x]), odd_end_map.floorEntry(end[x]).getValue(), val);
					Integer evenStart = even_start_map.higherKey(start[x]);
					if (evenStart != null && evenStart <= end[x]) {
						sts[0].update(1, 0, n - 1, even_start_map.get(evenStart), even_end_map.floorEntry(end[x]).getValue(), -val);
					}
				}
			}
			else {
				if (depth[x] == 0) {
					out.println(sts[0].query(1, 0, n - 1, even_start_map.get(start[x]), even_start_map.get(start[x])));
				}
				else {
					out.println(sts[1].query(1, 0, n - 1, odd_start_map.get(start[x]), odd_start_map.get(start[x])));
				}
			}
		}
		out.flush();
		out.close();
	}
	
	
	
	
	static int time = 0;
	static int even_idx = 0, odd_idx = 0;
	static void dfs (int node, int parent) {
		start[node] = time;
		dfs_tree[time] = node;
		if (depth[node] == 0){
			even_start_map.put(time, even_idx);
			even[even_idx++] = arr[node];
		}
		else {
			odd_start_map.put(time, odd_idx);
			odd[odd_idx++] = arr[node];
		}
		
//		System.out.println(node + " " + time);
		for (int child : tree[node]) 
			if (child != parent) {
				time++;
				depth[child] = 1 - depth[node];
				dfs(child, node);
			}
		
		if (depth[node] == 0) even_end_map.put(time, even_idx - 1);
		else odd_end_map.put(time, odd_idx -1);
		end[node] = time;
	}
	
	
	
//	4 12
//	1 2 3 4
//	1 2
//	2 3
//	3 4
//1 2 3
//2 1
//2 2
//2 3
//2 4
//2 4
//1 3 -1
//2 1
//2 2
//2 3
//2 4
//2 4
	


	static class ST  {
		int [] arr, lazy, tree;
		int n;
		ST (int a[]) {
			arr = a.clone();
			int pow = 0;
			n = a.length;
			while(1 << pow < n) pow++;
			tree = new int[1 << ++pow];
			lazy = new int[1 << pow];
			build(1, 0, n - 1);
//			System.out.println(Arrays.toString(arr));
//			System.out.println(Arrays.toString(tree));
		}
		
		void build (int node, int s, int e) {
			if (s == e) {
				tree[node] = arr[s];
			}
			else {
				int mid = (s + e) >> 1;
				build(node << 1, s, mid);
				build(node << 1 | 1 , mid + 1, e);
				tree[node] = tree[node << 1] + tree[node << 1 | 1];
			}
		}
		
		void update (int node, int s, int e, int l, int r, int val) {
			propagate(node, s, e);
			if (s >= l && e <= r) {
				tree[node] += (e - s + 1) * val;
				if (s != e) {
					lazy[node << 1] += val;
					lazy[node << 1 | 1] += val;
				}
			}
			else if (s > r || e < l);
			else {
				int mid = (s + e) >> 1;
				update(node << 1, s, mid, l, r, val);
				update(node << 1 | 1, mid + 1, e, l, r, val);
				tree[node] = tree[node << 1] + tree[node << 1 | 1];
			}
		}
		
		int query (int node, int s, int e, int l, int r) {
			propagate(node, s, e);
			if (s >= l && e <= r){
				return tree[node];
			}
			if (s > r || e < l) return 0;
			
			int mid = (s + e) >> 1;
			return query(node << 1, s, mid, l, r) + query(node << 1 | 1, mid + 1, e, l , r);
		}
		void propagate (int node, int s, int e) {
			if (lazy[node] != 0) {
				tree[node] += (e - s + 1) * lazy[node];
				if (s != e) {
					lazy[node << 1] += lazy[node];
					lazy[node << 1 | 1] += lazy[node];
				}
				lazy[node] = 0;
			}
		}
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public boolean nextEmpty() throws IOException {
			String s = nextLine();
			st = new StringTokenizer(s);
			return s.isEmpty();
		}
	}
}