問題文

$f(i)=A_i$ とします。また、$f(i)$ を $k$ 回合成したものを $f^k(i)$ とします。

頂点に $1$ から $N$ までの番号が付いた $N$ 頂点 $0$ 辺の有向グラフがあります。このグラフに以下の操作を行います。

• $1 \leq i \leq N,L \leq k \leq R$ について頂点 $i$ から頂点 $f^k(i)$ へ長さ $1$ の辺を張る。

このとき、$Q$ 個のクエリを順番に処理してください。$i$ 番目のクエリの内容は以下の通りです。

• 整数 $S_i,T_i$ が与えられる。頂点 $S_i$ から頂点 $T_i$ への最短距離を出力する。ただし、頂点 $S_i$ から頂点 $T_i$ へ到達できない場合は -1 と出力する。

制約

• $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$

入力

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

出力

最後に改行してください。

サンプル

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