You are given a directed graph with N vertices. The special thing about the graph is that each vertex has at most one outgoing edge. Your task is to answer the following two types of queries:

• 1 a delete the only edge outgoing from vertex a. It is guaranteed that the edge exists. 1 <= a <= N.
• 2 a b output the length of the shortest path from vertex a to vertex b, if the path exists. Otherwise output "-1" without quotes. 1 <= a, b <= N.

Input

First line of input contains a natural number N <= 10^5 the number of vertices in the graph.

The following line contains N integer numbers, i-th number is next[i] (0 <= next[i] <= N), meaning that there is an edge from vertex i to vertex next[i]. If next[i] = 0, assume that there is no outgoing edge from vertex i.

Third line contains a natural number M<=10^5 the number of queries.

The following M lines contain a query each. Queries are given in the manner described above.

Output

On the i-th line output the answer for the i-th query of type 2 a b.

Example

Input:
6
3 3 4 5 6 4
6
2 1 6
2 1 4
2 1 2
1 3
2 1 6
2 1 4

Output:
4
2
-1
-1
-1