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.*;
import java.util.*;
/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Ronak Vaghela
 */

public class KnightProblem2 {
	static int N;
	static ArrayList<Integer> adj[], weight[];
	static long depth[];
	static int dfsOrder[];
	static int timeIn[], timeOut[];
	static int time;
	static TreeMap<Long, Integer> dist;
	static long revMap[];
	static int dp[][];
	static ArrayList<Node> nodes;
	static int root[];

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		N = in.nextInt();
		adj = new ArrayList[N + 1];
		dp = new int[20][N + 1];

		weight = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			adj[i] = new ArrayList<Integer>();
		}
		int r = 0;
		for (int i = 1; i <= N; i++) {
			int s = in.nextInt();
			if (s == 0) {
				r = i;
			} else {
				adj[s].add(i);
			//	adj[i].add(s);

			}
		}

		depth = new long[N + 1];
		timeIn = new int[N + 1];
		timeOut = new int[N + 1];
		dfsOrder = new int[2 * N + 1];
		time = 0;
		dfs(r, 0, 1);
		preprocess();

		int Q = in.nextInt();
		root = new int[Q + 1];
		root[0] = 0;
		nodes = new ArrayList<Node>();
		nodes.add(new Node());
		
		for (int i = 1; i <= Q; i++) {
			int type = in.nextInt();
			if (type == 1) {
				int c = in.nextInt();
				root[i] = update(root[i - 1], 1, 2 * N, timeIn[c], 1);
				root[i] = update(root[i], 1, 2 * N, timeOut[c], -1);

			} else {
				int a = in.nextInt();
				int b = in.nextInt();
				int k = in.nextInt();
				int y = in.nextInt();
				root[i] = root[i - 1];
				out.println(solve(a, b, k, y + 1, i));
			}

		}
		out.close();
	}

	static long solve(int a, int b, int k, int y, int cur) {

		int lca = (lca(a, b));
		int av = verquery(cur, y - 1, a, a);
		int lcav = verquery(cur, y - 1, lca, lca);
		k += av;
		int p1 = verquery(cur, y - 1, a, lca);
		int p2 = verquery(cur, y - 1, b, lca);
		int all = p1 + p2 - lcav;
		// System.out.println(p1+" "+p2+" "+a+" "+b+" "+lca);
		if (all < k) {
			return -1;
		} else {
			int ans = -1;
			if (k <=p1) {
				// System.out.println(k+" "+p1);
				ans = getkth(k, cur, y - 1, a, lca);

			} else {

				k = k - p1;
				k = k + lcav;

				ans = getkth(p2 - k + 1, cur, y - 1, b, lca);
				// System.out.println(ans);
			}
			if (ans == b)
				ans = -1;

			return ans;
		}

	}

	static int getkth(int k, int t1, int t2, int a, int b) {
		if (depth[a] < depth[b]) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		// System.out.println(k+" "+t1+" "+t2+" "+a+" "+b);
		int sa = a;
		for (int i = logn-1; i >=0; i--) {
			if (depth[dp[i][a]] >= depth[b]
					&& verquery(t1, t2, sa, dp[i][a]) < k) {
				// System.out.println(verq(t1, t2, sa, dp[i][a])+" " +dp[i][a]);
				a = dp[i][a];
			}
		}
		if (depth[dp[0][a]] >= depth[b] && verquery(t1, t2, sa, dp[0][a]) < k) {
			a = dp[0][a];
		}

		return verquery(t1, t2, sa, a) == k ? a : dp[0][a];

	}

	static int verquery(int u1, int v1, int a, int b) {
		if (depth[a] > depth[b]) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		int cnt = (int) (depth[b] - depth[a] + 1 );
		return cnt- (query(root[u1], timeIn[a], timeIn[b], 1, 2 * N) - query(root[v1], timeIn[a], timeIn[b], 1, 2 * N));
	}

	static int query(int v, int l, int r, int ll, int rr) {

		if (v == 0)
			return 0;

		if (l == ll && rr == r)
			return sum(v);
		int xx = (ll + rr) / 2, res = 0;
		if (l <= xx)
			res += query(left(v), l, Math.min(r, xx), ll, xx);
		if (xx + 1 <= r)
			res += query(right(v), Math.max(xx + 1, l), r, xx + 1, rr);
		return res;
	}

	static int findKth(int start, int end, int leftRoot, int rightRoot, int k) {
		if (start == end)
			return start;
		int mid = (start + end) >> 1;
		int leftSum = sum(left(rightRoot)) - sum(left(leftRoot)); // number of
																	// nodes in
																	// [start,mid]
		if (leftSum >= k)
			return findKth(start, mid, left(leftRoot), left(rightRoot), k);
		else
			return findKth(mid + 1, end, right(leftRoot), right(rightRoot), k
					- leftSum);
	}

	static int update(int prevRoot, int start, int end, int x, int add) {
		Node now = new Node();
		now.sum = sum(prevRoot);
		now.left = left(prevRoot);
		now.right = right(prevRoot);
		nodes.add(now);
		int idx = nodes.size() - 1;
		if (start == end) {
			now.sum = add;
			return idx;
		}
		int mid = (start + end) >> 1;
		if (x <= mid) {
			int leftSon = left(prevRoot);
			now.left = update(leftSon, start, mid, x, add);
		} else {
			int rightSon = right(prevRoot);
			now.right = update(rightSon, mid + 1, end, x, add);
		}
		now.sum = sum(now.left) + sum(now.right);
		return idx;
	}

	static void dfs(int curr, int parent, long pathLength) {
		depth[curr] = pathLength;
		timeIn[curr] = ++time;
		dfsOrder[time] = curr;
		dp[0][curr] = parent;
		for (int i = 0; i < adj[curr].size(); i++) {
			int child = adj[curr].get(i);
			if (child != parent) {
				dfs(child, curr, pathLength + 1);
			}
		}
		timeOut[curr] = ++time;

	}

	static void preprocess() {

		for (int i = 1; i < 20; i++) {
			for (int j = 1; j <= N; j++) {
				dp[i][j] = dp[i - 1][dp[i - 1][j]];
			}
		}
	}

	static int logn = 20;

	static int lca(int a, int b) {
		if (depth[a] > depth[b]) {
			int temp = b;
			b = a;
			a = temp;
		}
		int d = (int) (depth[b] - depth[a]);
		for (int i = 0; i < logn; i++) {
			if ((d & (1 << i)) > 0) {
				b = dp[i][b];
			}
		}
		if (a == b) {
			return a;
		}
		for (int i = logn - 1; i >= 0; i--) {
			if (dp[i][a] != dp[i][b]) {
				a = dp[i][a];
				b = dp[i][b];
			}
		}
		return dp[0][a];
	}

	static long dist(int u, int v) {
		return depth[u] + depth[v] - 2 * depth[lca(u, v)];
	}

	static class Node {
		int sum, left, right;

		Node() {
			sum = 0;
			left = -1;
			right = -1;
		}
	}

	static int sum(int idx) {
		return idx == -1 ? 0 : nodes.get(idx).sum;
	}

	static int left(int idx) {
		return idx == -1 ? -1 : nodes.get(idx).left;
	}

	static int right(int idx) {
		return idx == -1 ? -1 : nodes.get(idx).right;
	}

	static void check(int start, int key, int end) {
		if (key < start || key > end)
			throw new RuntimeException();
	}

	static class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}