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.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    //Into the Hardware Mode
    int B = 20;
    void pre() throws Exception{}
    void solve(int TC)throws Exception{
        int n = ni();
        int[] from = new int[n-1], to = new int[n-1];
        for(int i = 0; i< n-1; i++){
            from[i] = ni()-1;to[i] = ni()-1;
        }
        int[][] g = makeU(n, from, to);
        SegTree t = new SegTree(n);
        int[] sub = new int[n], d = new int[n], chainHead = new int[n];
        int[][] ti = new int[2][n], par = new int[B][n];
        for(int b = 0; b< B; b++)Arrays.fill(par[b], -1);
        pre(g, par, d, sub, 0);
        time = -1;
        dfs(g, sub, ti, chainHead, 0, -1);
        for(int qq = ni(); qq> 0; qq--){
            int ty = ni(), u = ni()-1;
            if(ty == 1)
                t.update(ti[0][u], ti[1][u], 1);
            else if(ty == 2){
                while(u != -1){
                    t.update(ti[0][chainHead[u]], ti[0][u], 0);
                    u = par[0][chainHead[u]];
                }
            }else if(ty == 3){
                pn(t.query(ti[0][u]));
            }
        }
    }
//    int lift(int[][] par, int u, int d){
//        for(int b = B-1; b >= 0; b--)
//            if(((d>>b)&1)==1)
//                u = par[b][u];
//        return u;
//    }
//    int lca(int[][] par, int[] d, int u, int v){
//        if(d[u] > d[v])u = lift(par, u, d[u]-d[v]);
//        if(d[v] > d[u])v = lift(par, v, d[v]-d[u]);
//        if(u == v)return u;
//        for(int b = B-1; b >= 0; b--)
//            if(par[b][u] != par[b][v]){
//                u = par[b][u];
//                v = par[b][v];
//            }
//        return par[0][u];
//    }
    int time = -1;
    void dfs(int[][] g, int[] sub, int[][] ti, int[] chainHead, int u, int p){
        ti[0][u] = ++time;
        int hc = -1;
        for(int i = 0; i< g[u].length; i++){
            if(p == g[u][i])continue;
            if(hc == -1 || sub[g[u][i]] > sub[g[u][hc]])hc = i;
        }
        if(hc != -1){
            int tmp = g[u][hc];
            g[u][hc] = g[u][0];
            g[u][0] = tmp;
        }
        for(int v:g[u]){
            if(v == p)continue;
            if(v == g[u][0])chainHead[v] = chainHead[u];
            else chainHead[v] = v;
            dfs(g, sub, ti, chainHead, v, u);
        }
        ti[1][u] = time;
    }
    void pre(int[][] g, int[][] par, int[] d, int[] sub, int u){
        for(int b = 1; b< B; b++)
            if(par[b-1][u] != -1)
                par[b][u] = par[b-1][par[b-1][u]];
        sub[u]++;
        for(int v:g[u]){
            if(v == par[0][u])continue;
            par[0][v] = u;
            
            d[v] = d[u]+1;
            pre(g, par, d, sub, v);
            sub[u] += sub[v];
        }
    }
    class SegTree{
        int m = 1;
        int[] t, lazy;
        public SegTree(int n){
            while(m<= n)m<<=1;
            t = new int[m<<1];
            lazy = new int[m<<1];
            Arrays.fill(lazy, -1);
        }
        private void push(int ll, int rr, int i){
            if(lazy[i] != -1){
                if(ll == rr)t[i] = lazy[i];
                else{
                    lazy[i<<1] = lazy[i];
                    lazy[i<<1|1] = lazy[i];
                }
                lazy[i] = -1;
            }
        }
        int query(int p){
            return query(p, 0, m-1, 1);
        }
        private int query(int p, int ll, int rr, int i){
            push(ll, rr, i);
            if(ll == rr)return t[i];
            int mid = (ll+rr)/2;
            if(p <= mid)return query(p, ll, mid, i<<1);
            else return query(p, mid+1, rr, i<<1|1);
        }
        void update(int l, int r, int x){
            u(l, r, 0, m-1, 1, x);
        }
        private void u(int l, int r, int ll, int rr, int i, int x){
            push(ll, rr, i);
            if(l == ll && r == rr){
                lazy[i] = x;
                push(ll, rr, i);
                return;
            }
            int mid = (ll+rr)/2;
            push(ll, mid, i<<1);
            push(mid+1, rr, i<<1|1);
            if(r <= mid)u(l, r, ll, mid, i<<1, x);
            else if(l > mid)u(l, r, mid+1, rr, i<<1|1, x);
            else{
                u(l, mid, ll, mid, i<<1, x);
                u(mid+1, r, mid+1, rr, i<<1|1, x);
            }
        }
    }
    int[][] makeU(int n, int[] from, int[] to){
        int[] cnt = new int[n];int[][] g = new int[n][];
        for(int i:from)cnt[i]++;
        for(int i:to)cnt[i]++;
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< n-1; i++){
            g[from[i]][--cnt[from[i]]] = to[i];
            g[to[i]][--cnt[to[i]]] = from[i];
        }
        return g;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    long IINF = (long)1e18;
    final int INF = (int)1e9+2, MX = (int)2e6+5;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
    static boolean multipleTC = false, memory = false, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        if(fileIO){
            in = new FastReader("C:/users/user/desktop/inp.in");
            out = new PrintWriter("C:/users/user/desktop/out.out");
        }else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();
        for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}
 
    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }
 
        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }   
}