Беси практикуется в карточных фокусах. Она уже освоила Беси-тасование – тасование M (2 <= M <= 100,000) карт, так чтобы i-ая карта сверху становилась P[i]-ой картой сверху.
Теперь она переходит на бОльшие колоды. У неё есть колода из N (M <= N <= 1,000,000,000) карт, последовательно пронумерованных от 1 до N. Она тасует её следующим образом: берёт первые M карт, и выполняет их Беси-тасование, затем снова кладёт их наверх колоды. Далее она удаляет верхнюю карту из колоды и кладёт ее на стол значением вниз. Она повторяет этот процесс, выкладывая забираемые карты поверх друг друга, пока карты не кончатся. Когда у неё в исходной колоде остаётся меньше чем M карт, она прекращает выполнять Беси-тасование, но продолжает брать верхнюю карту и выкладывать её поверх ранее взятых.
Беси знает, что изначально колода находится в отсортированном порядке, Причём карта 1 наверху, карта 2 следующая и т.д. По заданному описанию Беси-тасования, вычислите какие карты окажутся на Q (1 <= Q <= N, Q <= 5,000) различных указанных позициях колоды.
В 50% тестов N<=100,000.
PROBLEM NAME: shufflegold
Формат входных данных
* Строка 1: Числа N, M и Q разделенные одиночными пробелами
* Строки 2..1+M: Строк i+1 указывает позицию сверху колоды, P[i], на которую переместиться i-ая карта после Беси-тасования (1 <= P[i] <= M).
* Строки 2+M..1+M+Q: Строка i+1+M содержит одно целое число qi описывающее i-ый запрос. Вы должны вычислить значение на карте, которая окажется в позиции qi сверху (1 <= qi <= N).
Формат выходных данных
* Строки 1..Q: На i-ой строке, выведите одно целое число, указывающее карту, которая окажется на позиции qi сверху.
Примечание
Тасование происходило так
[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (выкладываем 2 значением вниз) [3, 1, 4, 5] -> [1, 4, 3, 5] (выкладываем 1 значением вниз) [4, 3, 5] -> [3, 5, 4] (выкладываем 3 значением вниз) [5, 4] (выкладываем 5 значением вниз) [4] (выкладываем 4 значением вниз)
Финальный расклад [4, 5, 3, 1, 2]
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3 5
3
1
2
1
2
3
4
5
|
4
5
3
1
2
|