Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KAMELNEO - Kamelneon

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 ai. Profesor wyznaczył już wszystkie wartości ai, 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 ai (1≤ai≤n). Liczba ai (i-ta w kolejności) oznacza, iż po jednym impulsie garb i-ty przyjmuje kolor garbu ai. 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

Dodane przez:Rafal Nowak
Data dodania:2007-05-22
Limit czasu wykonania programu:0.100s-0.161s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO
Pochodzenie:Fajne Zawody Informatyczne
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.