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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.function.LongBinaryOperator;
import java.io.IOException;
import java.util.ArrayList;
import java.io.UncheckedIOException;
import java.util.List;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;
import java.util.function.IntFunction;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DWaterTree solver = new DWaterTree();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DWaterTree {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            HeavyLightDecompose hld = new HeavyLightDecompose(Long::sum, n, 0);
            for (int i = 0; i < n - 1; i++) {
                int a = in.ri() - 1;
                int b = in.ri() - 1;
                hld.addEdge(a, b);
            }
            hld.finish();
            int q = in.ri();
            for (int i = 0; i < q; i++) {
                int c = in.ri();
                int v = in.ri() - 1;
                if (c == 1) {
                    hld.updateSubtree(v, 1);
                } else if (c == 2) {
                    hld.updatePath(v, 0, 0);
                } else {
                    long ans = hld.processPath(v, v);
                    out.println(ans);
                }
            }
        }

    }

    static class HeavyLightDecompose {
        private LongBinaryOperator op;
        int n;
        int order = 1;
        HeavyLightDecompose.HLDNode root;
        HeavyLightDecompose.HLDNode[] nodes;
        HeavyLightDecompose.HLDNode[] segIndexToNode;
        HeavyLightDecompose.Segment segment;

        public HeavyLightDecompose(LongBinaryOperator op, int n, int rootId) {
            this.op = op;
            this.n = n;
            nodes = new HeavyLightDecompose.HLDNode[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new HeavyLightDecompose.HLDNode();
                nodes[i].id = i;
            }
            root = nodes[rootId];
        }

        public void addEdge(int a, int b) {
            nodes[a].next.add(nodes[b]);
            nodes[b].next.add(nodes[a]);
        }

        public void updateSubtree(int nodeId, long val) {
            HeavyLightDecompose.HLDNode node = nodes[nodeId];
            segment.update(node.dfsOrderFrom, node.dfsOrderTo, 1, n, val);
        }

        public void finish() {
            dfs(root, null);
            dfs2(root, root);
            segIndexToNode = new HeavyLightDecompose.HLDNode[n + 1];
            for (int i = 0; i < n; i++) {
                segIndexToNode[nodes[i].dfsOrderFrom] = nodes[i];
            }
            segment = new HeavyLightDecompose.Segment(1, n, i -> segIndexToNode[i]);
        }

        public long processPath(int uId, int vId) {
            HeavyLightDecompose.HLDNode u = nodes[uId];
            HeavyLightDecompose.HLDNode v = nodes[vId];
            long sum = 0;
            while (u != v) {
                if (u.link == v.link) {
                    if (u.size > v.size) {
                        HeavyLightDecompose.HLDNode tmp = u;
                        u = v;
                        v = tmp;
                    }
                    sum = op.applyAsLong(sum, segment.query(v.dfsOrderFrom + 1, u.dfsOrderFrom, 1, n, op));
                    u = v;
                } else {
                    if (u.link.size > v.link.size) {
                        HeavyLightDecompose.HLDNode tmp = u;
                        u = v;
                        v = tmp;
                    }
                    sum = op.applyAsLong(sum, segment.query(u.link.dfsOrderFrom, u.dfsOrderFrom, 1, n, op));
                    u = u.link.father;
                }
            }
            sum = op.applyAsLong(sum, segment.query(u.dfsOrderFrom, u.dfsOrderFrom, 1, n, op));
            return sum;
        }

        public void updatePath(int uId, int vId, long x) {
            HeavyLightDecompose.HLDNode u = nodes[uId];
            HeavyLightDecompose.HLDNode v = nodes[vId];
            while (u != v) {
                if (u.link == v.link) {
                    if (u.size > v.size) {
                        HeavyLightDecompose.HLDNode tmp = u;
                        u = v;
                        v = tmp;
                    }
                    segment.update(v.dfsOrderFrom + 1, u.dfsOrderFrom, 1, n, x);
                    u = v;
                } else {
                    if (u.link.size > v.link.size) {
                        HeavyLightDecompose.HLDNode tmp = u;
                        u = v;
                        v = tmp;
                    }
                    segment.update(u.link.dfsOrderFrom, u.dfsOrderFrom, 1, n, x);
                    u = u.link.father;
                }
            }
            segment.update(u.dfsOrderFrom, u.dfsOrderFrom, 1, n, x);
        }

        private static void dfs(HeavyLightDecompose.HLDNode root, HeavyLightDecompose.HLDNode father) {
            root.size = 1;
            root.father = father;
            for (HeavyLightDecompose.HLDNode node : root.next) {
                if (node == father) {
                    continue;
                }
                dfs(node, root);
                root.size += node.size;
                if (root.heavy == null || root.heavy.size < node.size) {
                    root.heavy = node;
                }
            }
        }

        private void dfs2(HeavyLightDecompose.HLDNode root, HeavyLightDecompose.HLDNode link) {
            root.dfsOrderFrom = order++;
            root.link = link;
            if (root.heavy != null) {
                dfs2(root.heavy, link);
            }
            for (HeavyLightDecompose.HLDNode node : root.next) {
                if (node == root.father || node == root.heavy) {
                    continue;
                }
                dfs2(node, node);
            }
            root.dfsOrderTo = order - 1;
        }

        public static class Segment implements Cloneable {
            private HeavyLightDecompose.Segment left;
            private HeavyLightDecompose.Segment right;
            private long val;
            private long dirty = -1;

            public void pushUp() {
            }

            public void modify(long x) {
                this.dirty = x;
                this.val = x;
            }

            public void pushDown() {
                if (dirty != -1) {
                    left.modify(dirty);
                    right.modify(dirty);
                    dirty = -1;
                }
            }

            public Segment(int l, int r, IntFunction<HeavyLightDecompose.HLDNode> function) {
                if (l < r) {
                    int m = DigitUtils.floorAverage(l, r);
                    left = new HeavyLightDecompose.Segment(l, m, function);
                    right = new HeavyLightDecompose.Segment(m + 1, r, function);
                    pushUp();
                } else {
                    val = function.apply(l).val;
                }
            }

            private boolean covered(int ll, int rr, int l, int r) {
                return ll <= l && rr >= r;
            }

            private boolean noIntersection(int ll, int rr, int l, int r) {
                return ll > r || rr < l;
            }

            public void update(int ll, int rr, int l, int r, long x) {
                if (noIntersection(ll, rr, l, r)) {
                    return;
                }
                if (covered(ll, rr, l, r)) {
                    modify(x);
                    return;
                }
                pushDown();
                int m = DigitUtils.floorAverage(l, r);
                left.update(ll, rr, l, m, x);
                right.update(ll, rr, m + 1, r, x);
                pushUp();
            }

            public long query(int ll, int rr, int l, int r, LongBinaryOperator op) {
                if (noIntersection(ll, rr, l, r)) {
                    return 0;
                }
                if (covered(ll, rr, l, r)) {
                    return val;
                }
                pushDown();
                int m = DigitUtils.floorAverage(l, r);
                return op.applyAsLong(left.query(ll, rr, l, m, op),
                        right.query(ll, rr, m + 1, r, op));
            }

            private void toString(StringBuilder builder) {
                if (left == null && right == null) {
                    builder.append("val").append(",");
                    return;
                }
                pushDown();
                left.toString(builder);
                right.toString(builder);
            }

            public String toString() {
                StringBuilder builder = new StringBuilder();
                deepClone().toString(builder);
                if (builder.length() > 0) {
                    builder.setLength(builder.length() - 1);
                }
                return builder.toString();
            }

            private HeavyLightDecompose.Segment deepClone() {
                HeavyLightDecompose.Segment seg = clone();
                if (seg.left != null) {
                    seg.left = seg.left.deepClone();
                }
                if (seg.right != null) {
                    seg.right = seg.right.deepClone();
                }
                return seg;
            }

            protected HeavyLightDecompose.Segment clone() {
                try {
                    return (HeavyLightDecompose.Segment) super.clone();
                } catch (CloneNotSupportedException e) {
                    throw new RuntimeException(e);
                }
            }

        }

        public static class HLDNode {
            List<HeavyLightDecompose.HLDNode> next = new ArrayList<>(2);
            int id;
            int dfsOrderFrom;
            int dfsOrderTo;
            int size;
            long val;
            HeavyLightDecompose.HLDNode link;
            HeavyLightDecompose.HLDNode heavy;
            HeavyLightDecompose.HLDNode father;

            public String toString() {
                return "" + id;
            }

        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append('\n');
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int floorAverage(int x, int y) {
            return (x & y) + ((x ^ y) >> 1);
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }
}

