課題
platypusの住む国はN個の都市があります。
各都市にはポータルと呼ばれる、
人や物をワープさせる便利な装置があります。
それぞれのポータルは一つ一つにワープできる都市が1つだけ登録されており、
使うことで登録されている都市にワープできます。
i番目の都市にあるポータルの移動先はP[i]です。
(この時、ポータル自体の都市にワープするポータルも存在しうることに注意してください)
国中にあるポータルは同時に「転移」という特殊な動作をすることがあります。
「転移」すると、すべてのポータルの移動先が、
「移動先のポータルの移動先」に代わります。
「転移」の性質を知りたいと思ったplatypusは、
Q個のクエリに答えようとしています。
j番目のクエリは、
「街中のポータルがS[j]回転移した後の、T[j]番目のポータルの移動先」
を問うものです。
platypusの代わりにクエリに応答するプログラムを作ってください。
入力
1行目には1つの整数Nが書かれている。
2行目にはi番目のポータルのワープ先のポータルの番号P[i]が空白区切りで書かれている。
3行目には1つの整数Qが書かれている。
4行目からQ行は、各行に２つの整数S[j],T[j]が空白区切りで書かれている。
出力
各クエリの答えを改行区切りで出力せよ
制限
- 1≦N≦100000(10^5)
- 1≦P[i]≦N
- 1≦Q≦100000(10^5)
- 1≦S[j]≦1000000000000000000(1018)
- 1≦T[j]≦N
20点分の入力は以下の条件を満たす。
- N≦1000
- Q≦1000
- S[i]≦1000
50点分の入力は以下の条件を満たす。
- Q≦1000
- S[i]≦1000
入出力例
入力例１
5 3 1 4 1 5 3 1 4 4 2 100 5
出力例１
3 1 5
一回転移すると、ポータルの移動先は「移動先にあるポータルの移動先」に代わるため、
ポータル1は移動先であるポータル3の移動先ポータル4に変更、
ポータル2は移動先であるポータル1の移動先ポータル3に変更、
ポータル3は移動先であるポータル4の移動先ポータル1に変更、
ポータル4は移動先であるポータル1の移動先ポータル3に変更、
ポータル5は移動先であるポータル5の移動先ポータル5に変更
されます。
１回転移した後、ポータル1はポータル3に向かうため、最初のクエリの答えは「3」です。
その後さらに3回転移し、合計4回転移すると、全てのポータルの移動先は初期配置に戻ります。
そのため、ポータル2はポータル1に向かい、２つ目のクエリの答えは「1」です。
最後に、ポータル5は何回転移したとしてもポータル5自身が移動先のため、
３つ目のクエリの答えは「5」です。
入力例２
10 3 1 4 1 5 9 2 6 5 3 5 1 2 3 4 5 6 7 8 9 10
出力例２
3 3 5 5 4
入力例３
2 2 2 1 1000000000 1
出力例３
2
入力例3は一部の部分点の制約を満たさないことに注意せよ。