ZOJ Problem Set - 3292
In the centerfield game of the second Revival Round in the Liar Game, Akiyama and Kikuchi played 17-Card Poker. The deck of cards in this game contained 4 A's, 4J's, 4 Q's, 4 K's and one Joker. The Joker could be used instead of any card. From best to worst, hands are ranked in the following order: five of a kind, royal straight flush, four of a kind, full house, straight, three of a kind, two pair, one pair. In each round, the banker opened a new pack of cards and shuffled the cards. Then Akiyama and Kikuchi cut the deck in turn, and the one who won the last round cut first, in case the banker might cheat. After that, the banker dealt the cards to them and they had their first bet. They discarded some of their own cards and got the same number of cards from the banker in turn and the second bet followed. At last they showed their hands and the one who had better hand won all the bets. After several rounds of exercise, Kikuchi found that he could find the place of Joker card after shuffling, with his remarkable sharp eyesight and wisual reflexes which allowed him to notice the white portions of the Ace and Joker cards. This gave a great advantage in the game against Akiyama. Yet Akiyama found this fact and managed to get the place of each card. He persuaded Kikuchi to admit that the banker used riffle shuffle instead of hindu shuffle, and tried to make the number of shuffle times a multiple of 4, which made the deck permute in their original order. Then he could get four of a kind while Kikuchi only got full house.
This time, Akiyama is to meet a more complex problem. The banker will use a m-riffle shuffle instead of original riffle shuffle. He asks you help him to calculate the order of deck after p times of shuffles.
Let us define it more formally. There are n cards in the deck. Each time, the banker takes out the downmost [n/m] cards form the deck and put them into the place that are the multiples of m(1-based). Here [x] means the greatest integer that is no greater than x. For example, when n=15 and m=4, the cards in the deck from downmost to topmost are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. After a shuffle, the deck will become 4, 5, 6, 1, 7, 8, 9, 2, 10, 11, 12, 3, 13, 14, 15. And after another shuffle, the deck will become 1, 7, 8, 4, 9, 2, 10, 5, 11, 12, 3, 6, 13, 14, 15.
There are at most 50 test cases in the input. Each test case contains 5 integers in one line: n m p a b. 1 < m <= n <= 50000, 1 <= p < 1000000000, 1 <= a <= b <= n, b-a <= 1000.
For each test case, output the original places of the cards that in place from a to b in one line, seperated by spaces.
15 4 1 2 7 15 4 2 2 7
5 6 1 7 8 9 7 8 4 9 2 10
Author: GUAN, Yao
Source: ZOJ Monthly, January 2010