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.util.*;
import java.io.*;
public class CF384E {
	public static void main(String[] args) throws IOException {
		in.init(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int n = in.nextInt();
		int m = in.nextInt();
		
		adj = new ArrayList[n];
		for(int i = 0; i < n; i ++)
			adj[i] = new ArrayList<Integer>();
		
		int[] a = new int[n];
		for(int i = 0; i < n; i ++)
			a[i] = in.nextInt();
		
		for(int i = 0; i < n-1; i ++)
		{
			int x = in.nextInt()-1;
			int y = in.nextInt()-1;
			adj[x].add(y);
			adj[y].add(x);
		}
		
		parent = new int[n];
		depth = new int[n];
		pre = new int[n];
		post = new int[n];
		index = 0;
		parent[0]=-1;
		precomp(0);
		
		BIT bit1 = new BIT(2*n);
		BIT bit2 = new BIT(2*n);
				
		for(int i = 0; i < n; i ++)
		{
			bit1.rangeUpdate(pre[i], pre[i], a[i]);
			bit2.rangeUpdate(pre[i], pre[i], a[i]);
		}
		
		for(int i = 0; i < m; i ++)
		{
			if(in.nextInt()==1)
			{
				int q = in.nextInt()-1;
				int v = in.nextInt();
				bit1.rangeUpdate(pre[q], post[q], depth[q]%2==0?v:-v);
				bit2.rangeUpdate(pre[q], post[q], depth[q]%2==0?-v:v);
				
			}
			else
			{
				int q = in.nextInt()-1;
				out.println(depth[q]%2==0?bit1.pointQuery(pre[q]):bit2.pointQuery(pre[q]));
			}
		}
		
		out.close();
	}
	static void precomp(int at)
	{
		pre[at]=index;
		index++;
		for(int to: adj[at])
		{
			if(to==parent[at])
				continue;
			parent[to] = at;
			depth[to] = depth[at]+1;
			precomp(to);
		}
		post[at]=index;
		index++;
	}
	static int index;
	static int[] parent;
	static int[] depth;
	static int[] pre;
	static int[] post;
	static ArrayList<Integer>[] adj;
	
	static class BIT
	{
		int[] tree;
		int n;
		BIT(int n)
		{
			tree = new int[n+1];
			this.n = n;
		}

		void pointUpdate(int x, int v)
		{
			x++;
			while(x<=n)
			{
				tree[x]+=v;
				x += (x&-x);
			}
		}
		
		int pointQuery(int x)
		{
			x++;
			int s = 0;
			while(x>0)
			{
				s += tree[x];
				x -= (x&-x);
			}
			return s;
		}

		void rangeUpdate(int x, int y, int val)
		{
			pointUpdate(x, val);
			if(y!=n)
				pointUpdate(y+1, -val);
		}
		
		public String toString()
		{
			int[] vals = new int[n];
			for(int i = 0; i < n; i ++)
				vals[i] = pointQuery(i);
			return Arrays.toString(vals);
		}
	}
	public static class in {
		static BufferedReader reader;
		static StringTokenizer tokenizer;

		static void init(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			tokenizer = new StringTokenizer("");
		}

		static String next() throws IOException {
			while (!tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}

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

		static double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

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

}
