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

public class R225QEPropogatingTree {

	static ArrayList<Integer> g[];
	static int n,m;
	static int a[],discovery[],begin[],end[],rev[],level[],aux[];
	static int segtree[];
	static int time,count;
	
	@SuppressWarnings("unchecked")
	public static void main(String args[] ) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    PrintWriter w = new PrintWriter(System.out);
	        
	    StringTokenizer st1 = new StringTokenizer(br.readLine());
	    n = ip(st1.nextToken());
		m = ip(st1.nextToken());
	          
	    StringTokenizer st2 = new StringTokenizer(br.readLine());
	    a = new int[n];
	    for(int i=0;i<n;i++)
	    	a[i] = ip(st2.nextToken());
	        
		g = new ArrayList[n];
	    for(int i=0;i<n;i++)
	    	g[i] = new ArrayList<Integer>();
	    
	    for(int i=1;i<n;i++){
	    	StringTokenizer st3 = new StringTokenizer(br.readLine());
	    	int v = ip(st3.nextToken()) - 1;
	    	int u = ip(st3.nextToken()) - 1;
	    	g[u].add(v);
	    	g[v].add(u);
	    }
	    
	    discovery = new int[n];
	    begin = new int[n];
	    end = new int[n];
	    level = new int[n];
	    aux = new int[n];
	    time = -1;
	    count = 0;
	    level[0] = 0;
	    dfs(0,-1);
	    
	   // System.out.println(Arrays.toString(discovery));
	   // System.out.println(Arrays.toString(begin));
	   // System.out.println(Arrays.toString(end));
	   // System.out.println(Arrays.toString(level));
	    rev = new int[n];
	    for(int i=0;i<n;i++)
	    	rev[discovery[i]] = i;
	    
	   // System.out.println(Arrays.toString(rev));
	    segtree = new int[4*n];
	    
	    for(int i=1;i<=m;i++){
	    	StringTokenizer st4 = new StringTokenizer(br.readLine());
	    	int type = ip(st4.nextToken());
	    	int x = ip(st4.nextToken()) - 1;
	    	
	    	if(type == 1){
	    		int val = ip(st4.nextToken());
	    		if(level[x] % 2 != 0)
	    			val *= -1;
	    		update(0,n-1,0,begin[x],val);
	    		if(end[x] + 1 != n)
	    			update(0,n-1,0,end[x] + 1,-1*val);
	    	}
	    	
	    	else{
	    		int ans = find(0,n-1,0,0,rev[x]);
	    		w.println(a[x] +( (level[x] % 2 == 0) ? ans : -1*ans));
	    	}
	    	
	    }
	    
	   // System.out.println(Arrays.toString(segtree));
	
	    
	    w.close(); 
	}
	
	public static void dfs(int curr,int parent){
		int s = g[curr].size();
		time++;
		discovery[count++] = curr; 
		begin[curr] = time;
		
		for(int i=0;i<s;i++){
			int nxt = g[curr].get(i);
			if(nxt != parent){
				level[nxt] = level[curr] + 1;
				dfs(nxt,curr);
			}
		}
		
		end[curr] = time;
	}
	
	public static void update(int s,int e,int c,int x,int val){
		if(s == e){
			segtree[c] += val;
			aux[s] += val;
			return;
		}
		int m = (s + e) / 2;
		if(x <= m)
			update(s,m,2*c+1,x,val);
		else
			update(m+1,e,2*c+2,x,val);
		segtree[c] += val;
	}
	
	public static int find(int s,int e,int c,int l,int r){
		if(s == l && e == r )
			return segtree[c];
		int m = (s + e) / 2;
		if(l <= m && r <= m)
			return find(s,m,2*c+1,l,r);
		if(l > m && r > m)
			return find(m+1,e,2*c+2,l,r);
		return find(s,m,2*c+1,l,m) + find(m+1,e,2*c+2,m+1,r);
	}
	
	public static int ip(String s){
		return Integer.parseInt(s);
	}
}
