Problem Statement

Let $f(i)=A_i$. Also, let $f^k(i)$ denote $f(i)$ composed $k$ times.

There is a directed graph with $N$ vertices and $0$ edges, whose vertices are numbered from $1$ to $N$. The following operation is performed on this graph.

• For $1 \leq i \leq N,L \leq k \leq R$, add an edge of length $1$ from vertex $i$ to vertex $f^k(i)$.

Process $Q$ queries in order. The $i$-th query is as follows.

• Integers $S_i,T_i$ are given. Output the shortest distance from vertex $S_i$ to vertex $T_i$. If vertex $T_i$ cannot be reached from vertex $S_i$, output -1.

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq A_i \leq N$
• $1 \leq L \leq R \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq S_i,T_i \leq N$
• $S_i ≠ T_i$

Input

$N\ L\ R$
$A_1\ A_2\ \dots \ A_N$
$Q$
$S_1 \ T_1$
$S_2 \ T_2$
$\vdots$
$S_Q \ T_Q$

Output

Print a newline at the end.

Sample

5 2 3
2 3 4 1 5
4
1 2
1 3
1 4
1 5

2
1
1
-1

3 3 3
2 3 1
3
1 2
2 3
3 1

-1
-1
-1

9 3 4
4 7 1 9 8 2 3 5 2
8
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9

1
3
2
-1
-1
1
-1
2