|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||55||16||13||32.500%|
Bessie is practicing her card tricks. She has already mastered the Bessie- shuffle -- a shuffle on M (2 <= M <= 100,000) cards that reorganizes the cards so the i-th card from the top is now the P[i]-th card from the top.
Now Bessie is practicing shuffles on larger decks. She has a deck of N cards (M <= N <= 1,000,000,000) conveniently labeled 1 to N. She shuffles this deck by taking the first M cards and performing the Bessie-shuffle on them, placing the shuffled cards back on top of the deck. She then removes the top card from the deck and places it face down. She repeats this process, placing the top cards successively on top of each other, until she is out of cards. When Bessie has less than M cards left, she no longer performs the Bessie-shuffle, but continues to place the top card on top of the others.
Bessie knows that the deck initially started in sorted order, with 1 on top, 2 next, and N on the bottom. Given the description of the Bessie-shuffle, help Bessie compute which cards end up located at Q different specified positions (1 <= Q <= N, Q <= 5,000) in the deck.
50% of test cases will have N <= 100,000.
5 3 5 3 1 2 1 2 3 4 5
4 5 3 1 2
Bessie has a deck of 5 cards initially ordered as [1, 2, 3, 4, 5]. Her shuffle is on 3 cards and has the effect of moving the top card to the bottom. There are 5 queries querying each position in the deck.
The shuffle proceeds as:
This produces the final order of [4, 5, 3, 1, 2]