Runda 2: Migający tłum

24.06.2009

Jest mroźna, grudniowa noc. Ciężkie chmury majestatycznie suną nad wrocławskim rynkiem pędzone zimnym, północnym wiatrem, ślady śpieszących gdzieś przechodniów co rusz odciskają się na białym puchu okrywającym zmarznięty bruk, a na zegarze ratuszowym dochodzi godzina dwudziesta pierwsza. Coraz liczniejsze sylwetki zaludniają rynek krążąc, wydawałoby się, bez celu, to wpatrując się w czarną otchłań nieba, to podziwiając lśniący w blasku latarni śnieg pod swoimi nogami. Z okien wyglądają mieszkańcy kamienic, leniwie obserwując ludzi snujących się w zadumie.

Przez okno wygląda też Alicja - z zawodu dziennikarka śledzcza, a prywatnie miłośniczka rebusów, zagadek i podchwytliwych pytań. Jej dociekliwy umysł nie śpi - przeciwnie, pozornie bezkształtny tłum przewijający się przez rynek zdaje się bardzo ją niepokoić. "Zazwyczaj o tej porze było dużo mniej ludzi," - myśli Alicja - "to musi coś oznaczać". Istotnie, intuicja przenikliwego obserwatora nie zawodzi. Gdy zegar zaczyna bić godzinę dziewiątą, tłum nagle ożywia się. Wszyscy zaczynają biegać, wyciagać coś pospiesznie z kieszeni, przepychać się na jakby z góry upatrzone pozycje. Istotnie już po chwili połowa osób zgromadzonych na rynku stoi w bardzo długim rzędzie, a każdy trzyma w ręce... świecącą kolorową żarówkę! Co więcej, kolor każdej żarówki jest inny (dla wygody osoby oraz żarówki ponumerujemy od 1 do n - w tej chwili i-ta osoba trzyma żarówkę o kolorze i)!

Jednak to nie koniec dziwów - po każdym uderzeniu zegara osoba stojąca na pozycji ai przekazuje swoją żarówkę osobie stojącej na pozycji i. Alicja jest zszokowana - przed jej oczami powstał właśnie migający tłum. Jednak zimna krew wraca już po chwili. Myśli pędzą niczym nieokiełznane ogiery, rozsypane fragmenty układanki łączą się w logiczną całość. Alicja już wie - to zaszyfrowana wiadomość od Boba! Zegar bije tylko dziewięć razy, jednak to wystarczyło Alicji, aby zapisać sposób przekazywania żarówek. Teraz pozostaje tylko odszyfrować wiadomość. Alicja musi wiedzieć, jaki kolor żarówki trzymałyby pewne osoby po pewnej ilości uderzeń zegara (uderzenia zegara liczymy łącznie z dziewięcioma uderzeniami, które rzeczywiście miały miejsce).

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna n (1 ≤ n ≤ 100 000) oznaczająca liczbę osób w tłumie. W drugim wierszu znajduje się n różnych liczb naturalnych ai (1 ≤ ain). Liczba ai (i-ta w kolejności) oznacza, iż po każdym uderzeniu zegara osoba i-ta otrzymuje żarówkę osoby ai. Następny wiersz składa się z jednej liczby naturalnej q (1 ≤ q ≤ 5000) oznaczającej liczbę zapytań Alicji. W każdym z kolejnych q wierszy znajduje się jedno zapytanie opisane za pomocą pary liczb naturalnych a, k oddzielonych spacją (1 ≤ an, 0 ≤ k ≤ 1 000 000 000), gdzie a oznacza numer osoby, k natomiast jest liczbą uderzeń zegara.

Wyjście

Wyjście powinno zawierać dokładnie q wierszy. i-ty wiersz powinien zawierać odpowiedź na i-te zapytanie: kolor żarówki, którą trzymałaby dana osoba po określonej ilości uderzeń zegara.

 

Przykład

Dla danych wejściowych

5
2 3 4 5 1
10
1 0
2 2
3 1
5 2
4 6
4 0
1 12345678
5 87654321
5 1
5 0

poprawną odpowiedzią jest

1
4
4
2
5
4
4
1
1
5

kod: FLASHMOB, limity: 1 s, 32 MB

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com