In Berland each feudal owns exactly one castle and each castle belongs to exactly one feudal.

Each feudal, except one (the King) is subordinate to another feudal. A feudal can have any number of vassals (subordinates).

Some castles are connected by roads, it is allowed to move along the roads in both ways. Two castles have a road between them if and only if the owner of one of these castles is a direct subordinate to the other owner.

Each year exactly one of these two events may happen in Berland.

  1. The barbarians attacked castle c. The interesting fact is, the barbarians never attacked the same castle twice throughout the whole Berlandian history. 
  2. A noble knight sets off on a journey from castle a to castle b (provided that on his path he encounters each castle not more than once). 



Let's consider the second event in detail. As the journey from a to b is not short, then the knight might want to stop at a castle he encounters on his way to have some rest. However, he can't stop at just any castle: his nobility doesn't let him stay in the castle that has been desecrated by the enemy's stench. A castle is desecrated if and only if it has been attacked after the year of y. So, the knight chooses the k-th castle he encounters, starting from a (castles a and b aren't taken into consideration), that hasn't been attacked in years from y + 1 till current year.

The knights don't remember which castles were attacked on what years, so he asked the court scholar, aka you to help them. You've got a sequence of events in the Berland history. Tell each knight, in what city he should stop or else deliver the sad news — that the path from city a to city b has less than k cities that meet his requirements, so the knight won't be able to rest.

Input

The first input line contains integer n (2 ≤ n ≤ 105) — the number of feudals. 

The next line contains n space-separated integers: the i-th integer shows either the number of the i-th feudal's master, or a 0, if the i-th feudal is the King. 

The third line contains integer m (1 ≤ m ≤ 105) — the number of queries.

Then follow m lines that describe the events. The i-th line (the lines are indexed starting from 1) contains the description of the event that occurred in year i. Each event is characterised by type ti (1 ≤ ti ≤ 2). The description of the first type event looks as two space-separated integers ti ci (ti = 1; 1 ≤ ci ≤ n), where ci is the number of the castle that was attacked by the barbarians in the i-th year. The description of the second type contains five space-separated integers: ti ai bi ki yi (ti = 2; 1 ≤ ai, bi, ki ≤ n; ai ≠ bi; 0 ≤ yi < i), where ai is the number of the castle from which the knight is setting off, bi is the number of the castle to which the knight is going, ki and yi are the k and y from the second event's description.

You can consider the feudals indexed from 1 to n. It is guaranteed that there is only one king among the feudals. It is guaranteed that for the first type events all values ci are different.

Output

For each second type event print an integer — the number of the castle where the knight must stay to rest, or -1, if he will have to cover the distance from ai to bi without a rest. Separate the answers by whitespaces.

Print the answers in the order, in which the second type events are given in the input.

Examples

Input

3
0 1 2
5
2 1 3 1 0
1 2
2 1 3 1 0
2 1 3 1 1
2 1 3 1 2


Output

2
-1
-1
2


Input

6
2 5 2 2 0 5
3
2 1 6 2 0
1 2
2 4 5 1 0


Output

5
-1

Note

In the first sample there is only castle 2 on the knight's way from castle 1 to castle 3. When the knight covers the path 1 - 3 for the first time, castle 2 won't be desecrated by an enemy and the knight will stay there. In the second year the castle 2 will become desecrated, so the knight won't have anywhere to stay for the next two years (as finding a castle that hasn't been desecrated from years 1 and 2, correspondingly, is important for him). In the fifth year the knight won't consider the castle 2 desecrated, so he will stay there again.
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.List;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE_Knights solver = new TaskE_Knights();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE_Knights {

    int n;
    static Graph g = new Graph();
    int[] parent;
    private LCA lca;
    private DFSOrder order;
    private PersistentSegmentTree tree;
    int[] marked;
    int[][] megaParent;
    private int[] level;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        n = in.nextInt();
        parent = new int[n];
        g.initGraph(n, n-1);
        int root = -1;
        for (int i = 0; i < n; ++i) {
            parent[i] = in.nextInt()-1;
            if (parent[i] != -1) {
                g.addDirectEdge(parent[i], i);
            } else {
                root = i;
            }
        }

        level = Parent.getVertexLevels(g, root, parent);
        megaParent = Parent.getLevelParents(g, root);
        order = new DFSOrder(g, root, parent);
        lca = new LCA(g, root, parent);

        marked = new int[n];
        Arrays.fill(marked, -1);

        int countQueries = in.nextInt();
        tree = new PersistentSegmentTree(countQueries + 5, n * 2 + 5);
        for (int i = 0; i < countQueries; ++i) {
            if (i != 0) {
                tree.newVersion();
            }
            int t = in.nextInt();
            if (t == 1) {
                int c = in.nextInt() - 1;
                tree.update(order.start(c), 1);
                tree.update(order.end(c), -1);
                marked[c] = i;
            } else {
//                for (int l = 0; l <= tree.curVersion; ++l) {
//                    out.println(l + " " + tree.getSum(l, 0, order.start(3) + 1));
//                    out.println(l + " " + tree.getSum(l, 0, order.start(0) + 1));
//                }
                int a = in.nextInt() - 1;
                int b = in.nextInt() - 1;
                int k = in.nextInt();
                int y = in.nextInt();
                int res = -1;
                int l = lca.LCA(a, b);

                if (l == a) {
                    l = getParent(b, level[b] - level[l] - 1);
                    int number = getNumber(b, l, y, tree.curVersion);
                    if (k <= number) {
                        k = number - k + 1;
                        res = calc(b, k, y, tree.curVersion, level[b] - level[l]);
                    } else {
                        res = -1;
                    }
                } else if (l == b) {
                    int number = getNumber(a, l, y, tree.curVersion);
                    if (number >= k) {
                        res = calc(a, k, y, tree.curVersion, level[a] - level[l]);
                    }
                } else {
                    int number = getNumber(a, l, y, tree.curVersion);
                    if (number >= k) {
                        res = calc(a, k, y, tree.curVersion, level[a] - level[l]);
                    } else {
                        k -= number;
                        l = getParent(b, level[b] - level[l] - 1);
                        number = getNumber(b, l, y, tree.curVersion);
                        if (k <= number) {
                            k = number - k + 1;
                            res = calc(b, k, y, tree.curVersion, level[b] - level[l]);
                        } else {
                            res = -1;
                        }

                    }
                }
                if (res == a || res == b) res = -1;
                if (res != -1) ++res;
                out.println(res);
            }
        }
    }

    private int calc(int fromV, int k, int y, int curVersion, int totalNumber) {
        int left = 1, right = totalNumber, middle;
        int res = -1;
        while (left <= right) {
            middle = (left + right) / 2;
            int v = getParent(fromV, middle);
            int cur = getNumber(fromV, v, y, curVersion);
            if (cur < k) {
                left = middle + 1;
            } else {
                res = v;
                right = middle - 1;
            }
        }
        return res;
    }

    private int getParent(int v, int dst) {
        for (int i = megaParent.length-1; i >= 0; --i) {
            if (megaParent[i][v] != -1) {
                if (dst >= (1 << i)) {
                    dst -= (1 << i);
                    v = megaParent[i][v];
                }
            }
        }
        return v;
    }

    private int getNumber(int v, int p, int y, int y2) {
        int totalNumberOfVertices = level[v] - level[p];
        int sumP = tree.getSumBetween(y, y2, 0, order.start(p)+1);
        int sumV = tree.getSumBetween(y, y2, 0, order.start(v)+1);
        int totalMarked = sumV - sumP;
        if (marked[v] >= y) {
            --totalMarked;
        }
        if (marked[p] >= y) {
            ++totalMarked;
        }
        return totalNumberOfVertices - totalMarked;
    }

    class PersistentSegmentTree {
        class Node {
            Node left = null;
            Node right = null;
            Node parent = null;

            int version;
            int rangeLeft, rangeRight;
            int myValue = 0;
            int sum = 0;

            Node copy() {
                Node copy = new Node();
                copy.left = this.left;
                copy.right = this.right;
                copy.rangeLeft = this.rangeLeft;
                copy.rangeRight = this.rangeRight;
                copy.myValue = this.myValue;
                copy.sum = this.sum;
                copy.parent = this.parent;
                return copy;
            }

            public int getMiddle() {
                return (rangeLeft + rangeRight) >> 1;
            }
        }

        Node[] roots;
        int curVersion;

        public PersistentSegmentTree(int versions, int size) {
            roots = new Node[versions + 1];
            Arrays.fill(roots, null);
            curVersion = 0;
            roots[0] = new Node();
            roots[0].rangeLeft = 0;
            roots[0].rangeRight = size;
            roots[0].version = 0;
        }

        void newVersion() {
            ++curVersion;
            roots[curVersion] = roots[curVersion-1].copy();
            roots[curVersion].version = curVersion;
        }

        int getSumBetween(int v1, int v2, int left, int right) {
            if (v1 == 0) {
                return getSum(v2, left, right);
            }
            return getSum(v2, left, right) - getSum(v1-1, left, right);
        }

        int getSum(int version, int left, int right) {
            return internalGetSum(roots[version], left, right);
        }

        private int internalGetSum(Node v, int left, int right) {
            if (v.rangeRight <= left || v.rangeLeft >= right) return 0;
            if (v.rangeLeft >= left && v.rangeRight <= right) {
                return v.sum;
            }
            int res = 0;
            if (v.left != null) {
                res += internalGetSum(v.left, left, right);
            }
            if (v.right != null) {
                res += internalGetSum(v.right, left, right);
            }
            return res;
        }

        void update(int pos, int value) {
            Node v = roots[curVersion];
            while (v.rangeLeft + 1 != v.rangeRight) {
                int middle = v.getMiddle();
                if (pos < middle) {
                    checkLeft(v, v.rangeLeft, middle);
                    v = v.left;
                } else {
                    checkRight(v, middle, v.rangeRight);
                    v = v.right;
                }
            }
            v.myValue = v.sum = value;
            v = v.parent;
            while (v != null) {
                v.sum = v.myValue + getSum(v.left) + getSum(v.right);
                v = v.parent;
            }
        }

        private int getSum(Node node) {
            if (node == null) return 0;
            return node.sum;
        }

        private void checkRight(Node v, int rangeLeft, int rangeRight) {
            if (v.right == null) {
                v.right = new Node();
                v.right.rangeLeft = rangeLeft;
                v.right.rangeRight = rangeRight;
                v.right.version = v.version;
                v.right.parent = v;
            }

            if (v.version != v.right.version) {
                Node t = v.right.copy();
                t.version = v.version;
                t.parent = v;
                v.right = t;
            }
        }

        private void checkLeft(Node v, int rangeLeft, int rangeRight) {
            if (v.left == null) {
                v.left = new Node();
                v.left.rangeLeft = rangeLeft;
                v.left.rangeRight = rangeRight;
                v.left.version = v.version;
                v.left.parent = v;
            }
            if (v.version != v.left.version) {
                Node t = v.left.copy();
                t.version = v.version;
                t.parent = v;
                v.left = t;
            }
        }
    }
}

class Graph {
    public int[] from;
    public int[] to;
    public int[] first;
    public int[] next;
    public int nVertex;
    public int nEdges;
    public int curEdge;

    public Graph() {}

    public void initGraph(int n, int m) {
        curEdge = 0;
        nVertex = n;
        nEdges = m;
        from = new int[m * 2];
        to = new int[m * 2];
        first = new int[n];
        next = new int[m * 2];
        Arrays.fill(first, -1);
    }

    public void addDirectEdge(int a, int b) {
        next[curEdge] = first[a];
        first[a] = curEdge;
        to[curEdge] = b;
        from[curEdge] = a;
        ++curEdge;
    }

}

class LCA {
    public int[] height;
    public int[] dfsOrder;
    public int[] posInDfsOrder;
    public int countDfsOrder;
    private int block;
    private int[][] blockTable;
    int logMaxList;
    int[] blockHash;
    int[][][] blockRmq;
    int[] log2;
    int[] parent;
    int n;

    public LCA(Graph tree, int root, int[] parent) {
        n = tree.nVertex;
        log2 = new int[2 * n];
        height = new int[n];
        Arrays.fill(height, -1);
        dfsOrder = new int[n*2-1];
        posInDfsOrder = new int[n];
        countDfsOrder = 0;
        this.parent = parent;
        dfsStack(tree, root);
        logMaxList = log(countDfsOrder);
        buildLCA();
    }

    // Walk graph
    private void dfsStack(Graph tree, int v) {
        int[] stackVertex = new int[tree.nVertex*2];
        int[] stackHeight = new int[tree.nVertex*2];
        int[] stackEdge = new int[tree.nVertex*2];
        int top = 0;
        stackHeight[top] = 0;
        stackVertex[top] = v;
        stackEdge[top] = tree.first[v];
        ++top;
        int currentHeight, edge;
        while (top > 0) {
            --top;
            v = stackVertex[top];
            currentHeight = stackHeight[top];
            edge = stackEdge[top];

            if (height[v] == -1) {
                height[v] = currentHeight;
                posInDfsOrder[v] = countDfsOrder;
                dfsOrder[countDfsOrder++] = v;
            } else {
                dfsOrder[countDfsOrder++] = v;
            }

            if (edge == -1) continue;

            int nextEdge = tree.next[edge];

            if (nextEdge != -1) {
                if (tree.to[nextEdge] == parent[v]) {
                    nextEdge = tree.next[nextEdge];
                }
            }

            stackHeight[top] = currentHeight;
            stackVertex[top] = v;
            stackEdge[top] = nextEdge;
            ++top;

            int u = tree.to[edge];
            stackHeight[top] = currentHeight + 1;
            stackVertex[top] = u;
            int edgeId = tree.first[u];
            if (edgeId != -1) {
                if (tree.to[edgeId] == v) {
                    edgeId = tree.next[edgeId];
                }
            }
            stackEdge[top] = edgeId;
            ++top;
        }
    }

    int log(int n) {
        int res = 1;
        while ((1 << res) < n)  ++res;
        return res;
    }

    // compares two indices in a
    int minHeight(int i, int j) {
        return height[dfsOrder[i]] < height[dfsOrder[j]] ? i : j;
    }

    // O(N) preprocessing
    void buildLCA() {
        block = (logMaxList + 1) / 2;
        int blocks = countDfsOrder / block + ((countDfsOrder % block > 0) ? 1 : 0);
        int maxBlocks = ((2 * n) / block) + 2;
        blockHash = new int[maxBlocks + 1];
        blockTable = new int[maxBlocks + 1][logMaxList + 1];
        blockRmq = new int[(int) (Math.sqrt(2*n) + 2)][block + 2][block + 2];
        ArrayUtils.fill(blockRmq, -1);
        ArrayUtils.fill(blockTable, -1);
        Arrays.fill(blockHash, 0);

        // precalc in each block and build sparse table
        for (int i = 0, blockId = 0, j = 0; i < countDfsOrder; ++i, ++j) {
            if (j == block) {
                j = 0;
                ++blockId;
            }
            if (blockTable[blockId][0] == -1 || minHeight(i, blockTable[blockId][0]) == i) {
                blockTable[blockId][0] = i;
            }
        }

        for (int j = 1; j <= logMaxList; ++j) {
            for (int i = 0; i < blocks; ++i) {
                int ni = i + (1 << (j - 1));
                if (ni >= blocks) {
                    blockTable[i][j] = blockTable[i][j - 1];
                } else {
                    blockTable[i][j] = minHeight(blockTable[i][j - 1], blockTable[ni][j - 1]);
                }
            }
        }

        // calc hashes of blocks
        for (int i = 0, blockId = 0, j = 0; i < countDfsOrder || j < block; ++i, ++j) {
            if (j == block) {
                j = 0;
                ++blockId;
            }
            if (j > 0 && (i >= countDfsOrder || minHeight(i - 1, i) == i - 1)) {
                blockHash[blockId] += (1 << (j - 1));
            }
        }

        // precalc RMQ inside each unique block
        for (int i = 0; i < blocks; ++i) {
            int id = blockHash[i];
            if (blockRmq[id][0][0] != -1) continue;
            for (int l = 0; l < block; ++l) {
                blockRmq[id][l][l] = l;
                for (int r = l + 1; r < block; ++r) {
                    blockRmq[id][l][r] = blockRmq[id][l][r-1];
                    if (i * block + r < countDfsOrder) {
                        blockRmq[id][l][r] = minHeight(i * block + blockRmq[id][l][r], i * block + r) - i * block;
                    }
                }
            }
        }

        // precalc logarithms
        for (int i = 0, j = 0; i < countDfsOrder; ++i) {
            if (1 << (j + 1) <= i) ++j;
            log2[i] = j;
        }
    }

    // answers RMQ in block #bl [l;r] in O(1)
    int LCAInBlocks(int blockId, int l, int r) {
        return blockRmq[blockHash[blockId]][l][r] + blockId * block;
    }

    // answers LCA in O(1)
    public int LCA(int v, int u) {
        int l = posInDfsOrder[v], r = posInDfsOrder[u];
        if (l > r) {
            int t = l;
            l = r;
            r = t;
        }
        int leftBlock = l / block, rightBlock = r / block;
        if (leftBlock == rightBlock) {
            return dfsOrder[LCAInBlocks(leftBlock, l % block, r % block)];
        }
        int ans1 = LCAInBlocks(leftBlock, l % block, block - 1);
        int ans2 = LCAInBlocks(rightBlock, 0, r % block);
        int ans = minHeight(ans1, ans2);
        if (leftBlock < rightBlock - 1) {
            int pw2 = log2[rightBlock-leftBlock-1];
            int ans3 = blockTable[leftBlock + 1][pw2];
            int ans4 = blockTable[rightBlock - (1 << pw2)][pw2];
            ans = minHeight(ans, minHeight(ans3, ans4));
        }
        return dfsOrder[ans];
    }

    // End of LCA
}

class DFSOrder {
    int[] start;
    int[] end;

    public DFSOrder(Graph tree, int root, int[] p) {
        start = new int[tree.nVertex];
        end = new int[tree.nVertex];
        buildDfsOrder(tree, root, p);
    }

    public int start(int v) {
        return start[v];
    }

    public int end(int v) {
        return end[v];
    }

    private void buildDfsOrder(Graph tree, int root, int[] p) {
        int[] stack = new int[2 * tree.nVertex];
        int top = 0;
        stack[top++] = (root + 1);
        int time = 0;
        while (top > 0) {
            --top;
            int v = stack[top];
            if (v < 0) {
                v = (-v) - 1;
                end[v] = time;
                ++time;
            } else {
                --v;
                start[v] = time++;
                stack[top++] = -(v+1);
                for (int i = tree.first[v]; i != -1; i = tree.next[i]) {
                    if (p[v] != tree.to[i]) {
                        stack[top++] = (tree.to[i] + 1);
                    }
                }
            }
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class Parent {
    public static int[] run(Graph tree, int root) {
        int[] parent = new int[tree.nVertex];
        int[] queue = new int[tree.nVertex];
        int front = 0, back = 0;
        queue[back++] = root;
        parent[root] = -1;
        while (front < back) {
            int v = queue[front++];
            for (int i = tree.first[v]; i != -1; i = tree.next[i]) {
                if (parent[v] != tree.to[i]) {
                    queue[back++] = tree.to[i];
                    parent[tree.to[i]] = v;
                }
            }
        }
        return parent;
    }

    public static int[][] getLevelParents(Graph tree, int root) {
        int maxLevel = 1;
        while ((1 << maxLevel) <= tree.nVertex) {
            ++maxLevel;
        }
        int[][] parent = new int[maxLevel][tree.nVertex];
        ArrayUtils.fill(parent, -1);
        parent[0] = Parent.run(tree, root);

        for (int level = 1; level < maxLevel; ++level) {
            for (int i = 0; i < tree.nVertex; ++i) {
                if (parent[level-1][i] != -1) {
                    int u = parent[level-1][i];
                    if (parent[level-1][u] != -1) {
                        int v = parent[level-1][u];
                        parent[level][i] = v;
                    }
                }
            }
        }
        return parent;
    }

    public static int[] getVertexLevels(Graph tree, int root, int[] parent) {
        int[] queue = new int[tree.nVertex];
        int front = 0, back = 0;
        queue[back++] = root;
        parent[root] = -1;
        int[] level = new int[tree.nVertex];
        level[root] = 0;
        while (front < back) {
            int v = queue[front++];
            for (int i = tree.first[v]; i != -1; i = tree.next[i]) {
                if (parent[v] != tree.to[i]) {
                    queue[back++] = tree.to[i];
                    level[tree.to[i]] = level[v] + 1;
                }
            }
        }
        return level;
    }
}

class ArrayUtils {

    public static void fill(int[][] f, int value) {
        for (int i = 0; i < f.length; ++i) {
            Arrays.fill(f[i], value);
        }
    }

    public static void fill(int[][][] a, int value) {
        for (int i = 0; i < a.length; ++i) {
            fill(a[i], value);
        }
    }

}

