SPOJ Problem Set (smpl)

1571. Kamelneon

Problem code: KAMELNEO

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.

1

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

Added by:

Rafał Nowak

Date:

2007-05-22

Time limit: 1s-5s
Source limit:50000B
Languages: All
Resource:

Fajne Zawody Informatyczne

2