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 Main{

    BufferedReader in;
    StringTokenizer str = null;
    PrintWriter out;

    private String next() throws Exception{
    	while (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
    
    private int nextInt() throws Exception{
	return Integer.parseInt(next());
    }
    
    int n, m, time = 1;
    int []tin, tout, a, level;
    List<Integer> g[];
    BIT even, odd;
    
    public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);
	
	n = nextInt();
	m = nextInt();
	
	a = new int[n];
	for(int i=0;i<n;i++) a[i] = nextInt();
	
	g = new LinkedList[n];
	for(int i=0;i<n;i++) g[i] = new LinkedList<Integer>();
	for(int i=0;i<n-1;i++){
	    int x = nextInt() - 1, y = nextInt() - 1;
	    g[x].add(y);
	    g[y].add(x);
	}
	
	tin = new int[n];
	tout = new int[n];
	level = new int[n];
	
	dfs(0, -1);
	
	/*
	System.out.println(Arrays.toString(a));
	System.out.println(Arrays.toString(tin));
	System.out.println(Arrays.toString(tout));
	System.out.println(Arrays.toString(level));
	*/
	
	even = new BIT(time+1);
	odd = new BIT(time+1);
	
	for(int i=0;i<m;i++){
	    int op = nextInt(), x = nextInt()-1;
	    if (op == 1){
		int val = nextInt();
		if (level[x] % 2 == 0){
		    even.update(tin[x], val);
		    even.update(tout[x], -val);
		    odd.update(tin[x], -val);
		    odd.update(tout[x], val);
		}else{
		    even.update(tin[x], -val);
		    even.update(tout[x], val);
		    odd.update(tin[x], val);
		    odd.update(tout[x], -val);
		}
	    }else{
		int r = a[x];
		if (level[x] % 2 == 0){
		    r+=even.sum(tin[x]);
		}else{
		    r+=odd.sum(tin[x]);
		}
		out.println(r);
	    }
	}
	
        out.close();
    }
    
    private void dfs(int x, int p){
	level[x] = (p == -1) ? 0 : (level[p]+1);
	tin[x] = time++;
	for(int i : g[x]){
	    if (p == i) continue;
	    dfs(i, x);
	}
	tout[x] = time++;
    }
    
    class BIT{
	int tree[];
	public BIT(int n){
	    tree = new int[n+1];
	}
	
	public void update(int x, int d){
	    while(x < tree.length){
		tree[x]+=d;
		x+=(x & -x);
	    }
	}
	
	public int sum(int x){
	    int ret = 0;
	    while(x > 0){
		ret+=tree[x];
		x-=(x & -x);
	    }
	    
	    return ret;
	}
    }
    
    public static void main(String args[]) throws Exception{
	new Main().run();
    }
}