베시 셔플 (골드)

베시는 베시 셔플을 완벽하게 익혔다. 이는 M장 (2 <= M <= 100,000)의 카드에 대한 셔플로, 위에서 i번째 카드가 위에서 P[i]번째 카드가 되도록 카드를 재배열한다.

이제 베시는 더 큰 덱으로 셔플을 연습하고 있다. 베시에게는 편의상 1부터 N까지의 라벨이 붙은 N장 (M <= N <= 1,000,000,000)의 카드로 이루어진 덱이 있다. 베시는 맨 위의 M장을 집어 베시 셔플을 수행한 뒤, 섞인 카드들을 덱 맨 위에 다시 올려놓는 방식으로 이 덱을 섞는다. 그다음 덱의 맨 위 카드를 빼서 뒤집어 내려놓는다. 이 과정을 반복하여 맨 위 카드를 차례로 서로의 위에 쌓아 올리며, 카드가 다 떨어질 때까지 계속한다. 남은 카드가 M장 미만이 되면 베시는 더 이상 베시 셔플을 수행하지 않지만, 맨 위 카드를 다른 카드들 위에 계속 올려놓는다.

덱은 처음에 정렬된 순서로 시작하며, 1이 맨 위, 2가 그다음, N이 맨 아래에 있다. 베시 셔플의 설명이 주어질 때, 덱에서 지정된 Q개 (1 <= Q <= N, Q <= 5,000)의 서로 다른 위치에 어떤 카드가 놓이게 되는지 계산하는 것을 도와주시오.

테스트 케이스의 50%는 N <= 100,000을 만족한다.

첫째 줄에 공백으로 구분된 N, M, Q가 주어진다.

둘째 줄부터 1+M번째 줄까지, i+1번째 줄에 베시 셔플에서 i번째 카드가 이동할 위에서부터의 위치 P[i]가 주어진다 (1 <= P[i] <= M).

2+M번째 줄부터 1+M+Q번째 줄까지, i+1+M번째 줄에 i번째 질의를 나타내는 정수 q_i가 하나 주어진다. 위에서 q_i번째 위치에 있는 카드의 라벨을 계산해야 한다 (1 <= q_i <= N).

첫째 줄부터 Q번째 줄까지, i번째 줄에 위에서 q_i번째 위치에 있는 카드를 나타내는 정수 하나를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > December > Gold