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.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.math.BigInteger;
import java.io.*;
import java.util.*;
public class Main {
	private static Reader fr;
	private static OutputStream out;
	private static final int delta = (int) 1e9 + 7;

	private static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[1024];
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}

		public int[] nextArray(int n) throws IOException {
			int arr[] = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}
	}

	private static void print(Object str) {
		try {
			out.write(str.toString().getBytes());
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	private static void println(Object str) {
		try {
			out.write((str.toString() + "\n").getBytes());
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	private static void printArray(int arr[]) {
		for (int val : arr) {
			print(val + " ");
		}
		println("");
	}

	private static long add(long a, long b) {
		return add(a, b, delta);
	}

	private static long add(long a, long b, long mod) {
		return ((a % mod) + (b % mod)) % mod;
	}

	private static long multiply(long a, long b) {
		return ((a % delta) * (b % delta)) % delta;
	}

	public static double multiply(double a, double b) {
		return ((a % delta) * (b % delta)) % delta;
	}

	private static long pow(int base, int pow) {
		if (pow == 0)
			return 1;
		if (pow == 1)
			return base;
		long halfPow = pow(base, pow / 2);
		if ((pow & 1) == 0)
			return multiply(halfPow, halfPow);
		return multiply(halfPow, multiply(base, halfPow));
	}

	private static long gcd(long a, long b) {
		if (a == 0 || b == 0)
			return a == 0 ? b : a;
		return gcd(b, a % b);
	}

	private static long kadane(int[] arr) {
		int size = arr.length;
		long max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

		for (int anArr : arr) {
			max_ending_here = max_ending_here + anArr;
			if (max_so_far < max_ending_here)
				max_so_far = max_ending_here;
			if (max_ending_here < 0)
				max_ending_here = 0;
		}
		return max_so_far;
	}

	public static void main(String args[]) throws IOException {
		run();
	}

	private static void run() throws IOException {
		fr = new Reader();
		out = new BufferedOutputStream(System.out);
		solve();
		out.flush();
		out.close();
	}
	static int mod=1000000007;
	static int cnt=0;
	static int ans=0;
	private static void solve() throws IOException 
	{
		int t = 1;//fr.nextInt();
		while (t-- > 0) {
			int n = fr.nextInt();
			int m = fr.nextInt();
			ArrayList<Integer>[] g= new ArrayList[n];
            for (int i = 0; i < n; i++) 
                g[i] =new ArrayList<Integer>(); 
            int a[]=new int[n];
            int f[]=new int[n];
            int e[]=new int[n];
            int b[]=new int[n];
            int l[]=new int[n];
            int st[][]=new int[2][4*n];
            for(int i=0;i<n;i++)
                a[i]=fr.nextInt();
            for(int i=0;i<n-1;i++)
            {
                int u=fr.nextInt()-1;
                int v=fr.nextInt()-1;
                g[u].add(v);
                g[v].add(u);
            }
            task0(g,f,e,b,l,n,0,-1,0);
            while(m-->0)
            {
                int ch = fr.nextInt();
                if(ch==1)
                {
                   int x = fr.nextInt()-1;
                   int v = fr.nextInt();
                    update(st,l,0,n-1,f[x],e[x],0,v,x);    
                    // print2(st[0],4*n);   
                    // print2(st[1],4*n);   
                }
                else
                {
                    int x = fr.nextInt()-1;
                    ans=0;
                    get(st,l,0,n-1,f[x],0,x);
                    //System.out.println("Done!!!");
                    System.out.println(ans+a[x]);
                }
            }
            // print2(b,n);
            // print2(f,n);
            // print2(e,n);
            // print2(l,n);
            // System.out.println("Done!!!");
		}
    }
    
    static void update(int st[][],int lev[],int s,int e,int l,int r,int x,int v,int k)
    {
        if(l>e||r<s)
            return ;
        if(s>=l&&e<=r)
        {
            st[lev[k]][x]+=v;
            st[lev[k]^1][x]-=v;
            //System.out.println(x+" "+r);
            return;
        }
        int mid=(s+e)/2;
        update(st,lev,s,mid,l,r,2*x+1,v,k);
        update(st,lev,mid+1,e,l,r,2*x+2,v,k);
    }
    
    static void get(int st[][],int lev[],int s,int e,int u,int x,int k)
    {
        //System.out.println(st[lev[u]][x]+" "+u);
        ans+=st[lev[k]][x];
        if(s==e)
            return ;
        else
        {
            int mid = (s+e)/2;
    		if(u<=mid && u>=s)
    			get(st,lev,s,mid,u,2*x+1,k);
    		else
    			get(st,lev,mid+1,e,u,2*x+2,k);
        }
    }
    
    static void task0(ArrayList<Integer>[] g ,int f[],int e[],int b[],int l[],int n,int s,int p,int x)
    {
        //System.out.println(s+1);
        b[cnt]=s;
        f[s]=cnt++;
        l[s]=x%2;
        for(int i=0;i<g[s].size();i++)
            if(g[s].get(i)!=p)
                task0(g,f,e,b,l,n,g[s].get(i),s,x+1);
        e[s]=cnt-1;
    }
    
    static void print1(ArrayList<Integer>[] g,int n)
    {
        for(int i=0;i<n;i++)
        {
            System.out.print(i+"\t");
            for(int j=0;j<g[i].size();j++)
                System.out.print(g[i].get(j)+" ");
            System.out.println();
        }
    }
    static void print2(int a[],int n)
    {
        for(int i=0;i<n;i++)
            System.out.print(a[i]+"\t");
        System.out.println();
    
    }
}