POLSKI SPOJ

Profesor Jacob prowadzi na jednej z wysp Oceanu Spokojnego badania w ramach projektu Dharma. Podczas jednej ze swoich nocnych przechadzek po dżungli natknął się coś, co mogło być tylko nieznanym do tej pory nauce gatunkiem jaszczurki. Zwierzę wyglądem przypominające przewód z lampkami choinkowymi wnet stało się głównym przedmiotem badań Jacoba. Po tygodniu ciężkiej pracy profesor zanotował kilka bardzo interesujących cech okazu, które skłoniły go do nazwania owego stworzenia kamelneonem.

Kamelneon przypominał gąsienicę zbudowaną z wielu świecących garbów, z których żadne dwa nie miały takiej samej barwy. Profesor ponumerował wszystkie garby oraz ich kolory kolejnymi liczbami naturalnymi 1,2,...,n (i-ty garb początkowo miał kolor o numerze i). Chcąc dokładnie zbadać stworzenie, Jacob postanowił zastosować starą i wielokrotnie sprawdzoną metodę elektrowstrząsów. Kamelneon pobudzony dokładnie jednym impulsem elektrycznym zmienia jednocześnie kolory wszystkich swoich garbów w następujący sposób: nowym kolorem garbu i staje się stary kolor garbu a_i. Profesor wyznaczył już wszystkie wartości a_i, jednak do ukończenia badań potrzebne mu są informacje o tym, jak zmieniają się kolory po zadziałaniu większą ilościa impulsów. I tutaj właśnie przyda się Twoja pomoc.

Zadanie

Znając zachowanie kamelneona potraktowanego jednym impulsem, odpowiedz na pytania profesora dotyczące zmian kolorów konkretnych garbów.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna n (1≤n≤100 000) oznaczająca liczbę garbów kamelneona. W drugim wierszu znajduje się n różnych liczb naturalnych a_i (1≤a_i≤n). Liczba a_i (i-ta w kolejności) oznacza, iż po jednym impulsie garb i-ty przyjmuje kolor garbu a_i. Następny wiersz składa się z jednej liczby naturalnej q (1≤q≤5000) oznaczającej liczbę zapytań profesora. W każdym z kolejnych q wierszy znajduje się jedno zapytanie opisane za pomocą pary liczb naturalnych a,k oddzielonych spacją (1≤a≤n, 0≤k≤1000000000), gdzie a oznacza numer garbu, k natomiast jest liczbą impulsów, którymi częstujemy kamelneona.

Wyjście

Wyjście powinno zawierać dokładnie q wierszy. i-ty wiersz powinien zawierać odpowiedź na i-te zapytanie: kolor, jaki przybrał dany garb po zadziałaniu podaną liczbą impulsów.

Przykład

Wejście

10
2 1 5 4 8 9 3 7 6 10
5
4 10
1 0
3 15
7 1
6 9

Wyjście

4
1
7
3
9