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;


public class Abood3A {

	static int V, start[], end[], c;
	static boolean[] even;
	static ArrayList<Integer>[] Tree;

	static void dfs(int u , int p, boolean e) {
		start[u] = c;

		for (int i = 0; i < Tree[u].size(); i++) {
			int v = Tree[u].get(i);

			if(v != p)
				dfs(v, u, !e);
		}

		even[c] = e;
		end[u] = c++;
	}

	static class SegmentTree {

		int N;
		long[] array, sTree, lazy;

		SegmentTree(long[] in)		
		{
			array = in; N = in.length - 1;
			sTree = new long[N<<1];
			lazy = new long[N<<1];
			build(1,1,N);
		}

		void build(int node, int b, int e)
		{
			if(b == e)					
				sTree[node] = array[b];
			else						
			{
				int mid = b + e >> 1;
			build(node<<1,b,mid);
			build(node<<1|1,mid+1,e);
			}
		}



		void update_range(int i, int j, long val)		// O(log n) 
		{
			update_range(1,1,N,i,j,val);
		}

		void update_range(int node, int b, int e, int i, int j, long val)
		{
			if(i > e || j < b)		
				return;
			if(b >= i && e <= j)		
			{	
				lazy[node] += val;				
			}							
			else		
			{
				int mid = b + e >> 1;
			propagate(node);
			update_range(node<<1,b,mid,i,j,val);
			update_range(node<<1|1,mid+1,e,i,j,val);
			}

		}
		void propagate(int node)		
		{
			lazy[node<<1] += lazy[node];
			lazy[node<<1|1] += lazy[node];	
			lazy[node] = 0;
		}

		long query(int i)
		{
			return query(1,1,N,i);
		}

		long query(int node, int b, int e, int i)	// O(log n)
		{
			if(i>e || i <b)
				return 0;		
			if(b>= i && e <= i) {
				return sTree[node] + (even[i] ? lazy[node] : -lazy[node]);
			}
			int mid = b + e >> 1;
			propagate(node);
			long q1 = query(node<<1,b,mid,i);
			long q2 = query(node<<1|1,mid+1,e,i);
			return q1 + q2;	

		}


	}



	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		V = sc.nextInt();
		int m = sc.nextInt();
		
		int N = 1; while(N < V) N <<= 1; //padding

		long[] tmp = new long[N + 1];
		for(int i = 1; i <= V; i++)
			tmp[i] = sc.nextInt();
		
		c = 1;
		start = new int[V + 1];
		end = new int[V + 1];
		even = new boolean[V + 1];
		
		Tree = new ArrayList[V + 1];
		
		for (int i = 1; i <= V; i++)
			Tree[i] = new ArrayList<>();
		
		for (int i = 0; i < V - 1; i++) {
			int f = sc.nextInt();
			int t = sc.nextInt();
			
			Tree[f].add(t);
			Tree[t].add(f);
		}
		dfs(1, -1, true);
		
		long[] in = new long[N + 1];
		
		for(int i = 1; i <= V; i++)
			in[end[i]] = tmp[i];
		
		SegmentTree st = new SegmentTree(in);
		
		for (int i = 0; i < m; i++) {
			int t = sc.nextInt();
			
			if(t == 1) {
				int x = sc.nextInt();
				long val = sc.nextInt();
				
				if(even[end[x]])
					st.update_range(start[x], end[x], val);
				else
					st.update_range(start[x], end[x], -val);
				
			}else 
				out.println(st.query(end[sc.nextInt()]));
		}

		out.flush();

	}




	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();}



	}

}