Mad scientist Mike has constructed a rooted tree, which consists of n vertices. Each vertex is a reservoir which can be either empty or filled with water.

The vertices of the tree are numbered from 1 to n with the root at vertex 1. For each vertex, the reservoirs of its children are located below the reservoir of this vertex, and the vertex is connected with each of the children by a pipe through which water can flow downwards.

Mike wants to do the following operations with the tree: 

  1. Fill vertex v with water. Then v and all its children are filled with water. 
  2. Empty vertex v. Then v and all its ancestors are emptied. 
  3. Determine whether vertex v is filled with water at the moment. 

Initially all vertices of the tree are empty.

Mike has already compiled a full list of operations that he wants to perform in order. Before experimenting with the tree Mike decided to run the list through a simulation. Help Mike determine what results will he get after performing all the operations.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 500000) — the number of vertices in the tree. Each of the following n - 1 lines contains two space-separated numbers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the edges of the tree.

The next line contains a number q (1 ≤ q ≤ 500000) — the number of operations to perform. Each of the following q lines contains two space-separated numbers ci (1 ≤ ci ≤ 3), vi (1 ≤ vi ≤ n), where ci is the operation type (according to the numbering given in the statement), and vi is the vertex on which the operation is performed.

It is guaranteed that the given graph is a tree.

Output

For each type 3 operation print 1 on a separate line if the vertex is full, and 0 if the vertex is empty. Print the answers to queries in the order in which the queries are given in the input.

Examples

Input

5
1 2
5 1
2 3
4 2
12
1 1
2 3
3 1
3 2
3 3
3 4
1 2
2 4
3 1
3 3
3 4
3 5


Output

0
0
0
1
0
1
0
1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.PrintWriter;
import java.util.ArrayList;
public class D343 
{
    static class SegmentTree
    {
        int n;
        boolean tree[];
        int start[];
        int end[];
        int lazy[];
        public SegmentTree(int n)
        {
            this.n=n;
            tree=new boolean[4*n+1];
            start=new int[4*n+1];
            end=new int[4*n+1];
            lazy=new int[4*n+1];
            initialize(1,0,n-1);
        }
        void initialize(int node,int s,int e)
        {
            start[node]=s;
            end[node]=e;
            lazy[node]=-1;
            if(s==e)
            {
                return;
            }
            
            int mid=(s+e)/2;
            initialize(2*node,s,mid);
            initialize(2*node+1,mid+1,e);
        }
        void lazyPropagation(int node)
        {
            if(lazy[node]==-1)
                return;
            lazy[2*node]=lazy[node];
            lazy[2*node+1]=lazy[node];
            lazy[node]=-1;
            //0->and with 0,1->or with 1
        }
        void update(int node)
        {   
            boolean leftValue,rightValue;
            if(lazy[2*node]==0)
                leftValue=false;
            else if(lazy[2*node]==1)
                leftValue=true;
            else
                leftValue=tree[2*node];
            if(lazy[2*node+1]==0)
                rightValue=false;
            else if(lazy[2*node+1]==1)
                rightValue=true;
            else
                rightValue=tree[2*node+1];
            tree[node]=(leftValue||rightValue);
        }
        void incrementRange(int l,int r,int value)
        {
            incrementRange(1,l,r,value);
        }   
        void incrementRange(int node,int l,int r,int value)
        {
            if(start[node]>r||end[node]<l)
                return;
            if(start[node]>=l&&end[node]<=r)
            {
                lazy[node]=value;
                return;
            }
            lazyPropagation(node);
            incrementRange(2*node,l,r,value);
            incrementRange(2*node+1,l,r,value);
            update(node);
            
        }
        boolean query(int l,int r)
        {
            return query(1,l,r);
        }
        boolean query(int node,int l,int r)
        {
            if(start[node]>r||end[node]<l)
                return false;
            if(start[node]>=l&&end[node]<=r)
            {
                if(lazy[node]==0)
                    return false;
                else if(lazy[node]==1)
                    return true;
                else
                    return tree[node];
            }
            lazyPropagation(node);
            boolean leftValue=query(2*node,l,r);
            boolean rightValue=query(2*node+1,l,r);
            update(node);
            return leftValue||rightValue;
        }
    }
    
    static ArrayList<Integer> g[];//graph
    static int p[];//parent
    static int h[];//height
    static int ch[];//chain head
    static int pos[];//position in segment tree
    static int end[];
    static int sc[];//special child
    static int time;
    static boolean dn=false;
    static void clear(int n)//intitialize each test case
    {
        if(!dn)
        {
            gen(n);//initialize first case
            dn=true;
            return;
        }
        time=-1;
        for(int i=0;i<=n;i++)
        {
            g[i].clear();
            p[i]=h[i]=ch[i]=sc[i]=pos[i]=end[i]=0;
        }
        
    }
    static void gen(int n)//initialize first case
    {
        g=new ArrayList[n+1];
        for(int i=0;i<=n;i++)
        {
            g[i]=new ArrayList<>();
        }
        p=new int[n+1];
        h=new int[n+1];
        ch=new int[n+1];
        sc=new int[n+1];
        pos=new int[n+1];
        end=new int[n+1];
        time=-1;
    }
    static int dfs1(int n,int ht)//dfs to calculate height and sppecial child n is node ,ht is height
    {
        h[n]=ht;
        int count=1,maxcount=0;
        for(int i=0;i<g[n].size();i++)
        {
            int nn=g[n].get(i);
            if(nn==p[n])
                continue;
            p[nn]=n;
            int uu=dfs1(nn,ht+1);
            if(uu>maxcount)
            {
                maxcount=uu;
                sc[n]=nn;
            }
            count+=uu;
        }
        return count;
    }
    static void dfs2(int par,int n)//dfs to perform hld par is parent,n is node
    {
        pos[n]=++time;
        if(sc[par]==n)
        {
            ch[n]=ch[par];
        }
        else
        {
            ch[n]=n;
        }
        if(sc[n]!=0)
            dfs2(n,sc[n]);
        for(int nn:g[n])
        {
            if(nn==p[n]||nn==sc[n])
                continue;
            dfs2(n,nn);
        }
        end[n]=time;
    }
        
    static void solve() throws IOException
    {
        Scanner in=new Scanner(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int t=1;
        while(t--!=0)
        {
            int n=in.nextInt();
            clear(n);
            for(int i=1;i<n;i++)
            {
                int u=in.nextInt(),v=in.nextInt();
                g[u].add(v);
                g[v].add(u);
            }
            dfs1(1,1);
            dfs2(0,1);
            SegmentTree st=new SegmentTree(n);
            int m=in.nextInt();
            
            while(m-->0)
            {
                int xx=in.nextInt();
                if(xx==2)
                {
                    int u=in.nextInt();
                    int v=1;
                    while(true)
                    {
                        if(ch[u]==ch[v])//u and v lie in same chain
                        {
                            if(pos[u]>pos[v])//Why?
                            {
                                int y=u;u=v;v=y;//swap u,v
                            }
                            st.incrementRange(pos[u], pos[v],0);
                            break;
                        }
                        else//u and v lie in different chains
                        {
                            if(h[ch[u]]<h[ch[v]])//why?
                            {
                                int x=u;u=v;v=x;//swap u,v;
                            }
                            st.incrementRange(pos[ch[u]], pos[u],0);
                            u=p[ch[u]];
                        }
                    }
                }
                else if(xx==1)
                {
                    int u=in.nextInt();
                    st.incrementRange(pos[u],end[u],1);
                }
                else
                {
                    
                    int u=in.nextInt();
                    boolean ans=st.query(pos[u],pos[u]);
                    out.println(ans?1:0);
                }
            }
        }
        out.close();
    }
    /*------------------------------------done-------------------------------------------*/
    
    
    static class Scanner
    {
        BufferedReader br;
        StringTokenizer tk=new StringTokenizer("");
        public Scanner(InputStream is) 
        {
            br=new BufferedReader(new InputStreamReader(is));
        }
        public int nextInt() throws IOException
        {
            if(tk.hasMoreTokens())
                return Integer.parseInt(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextInt();
        }
        public long nextLong() throws IOException
        {
            if(tk.hasMoreTokens())
                return Long.parseLong(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextLong();
        }
        public String next() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return next();
        }
        public String nextLine() throws IOException
        {
            tk=new StringTokenizer("");
            return br.readLine();
        }
        public double nextDouble() throws IOException
        {
            if(tk.hasMoreTokens())
                return Double.parseDouble(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextDouble();
        }
        public char nextChar() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken().charAt(0));
            tk=new StringTokenizer(br.readLine());
            return nextChar();
        }
        public int[] nextIntArray(int n) throws IOException
        {
            int a[]=new int[n];
            for(int i=0;i<n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArray(int n) throws IOException
        {
            long a[]=new long[n];
            for(int i=0;i<n;i++)
                a[i]=nextLong();
            return a;
        }
        public int[] nextIntArrayOneBased(int n) throws IOException
        {
            int a[]=new int[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArrayOneBased(int n) throws IOException
        {
            long a[]=new long[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextLong();
            return a;
        }
    
    
    }
    
    public static void main(String args[]) throws IOException
    {
        new Thread(null, new Runnable() {
            public void run() {
                try
                {
                    solve();
                }
                catch(Exception e)
                {
                    e.printStackTrace();
                }
            }
        }, "1", 1 << 26).start();
        
    }
}
