Card Stacking

Time limit1sMemory limit128 MB

Summary
Simulate a deck where each dealt card is followed by moving P cards to the bottom, and report the original positions that reach Bessie.
Level

Medium4 of 10

Topics
Simulation, Queue, Implementation, Math
Solved
No attempts yet

Problem

Bessie is playing a card game together with her N−1N-1 cow friends, so there are NN players in total (2≤N≤1002 \le N \le 100). They use a deck of KK cards (N≤K≤100 000N \le K \le 100\,000, and KK is a multiple of NN). Exactly M=K/NM = K/N of the cards are "good" and the remaining K−MK-M are "bad".

Bessie is the dealer and naturally wants to keep every "good" card for herself. Her friends suspect she will cheat, so they force her to deal by the following rules:

  1. Deal the card on the top of the deck to the cow on Bessie's right.
  2. Every time she deals one card, she must move the next PP cards (1≤P≤101 \le P \le 10) from the top of the deck to the bottom.
  3. Continue dealing to each player in turn, going counterclockwise.

Because Bessie starts by dealing to the cow on her right and she herself sits last in the counterclockwise order, she receives every NN-th card that is dealt.

The cards are numbered 1,2,…1, 2, \dots from the top of the original deck. Determine the positions in the original deck where the "good" cards must be placed so that Bessie ends up with all of them.

Input

The first line contains three space-separated integers NN, KK, and PP.

Output

Print the M=K/NM = K/N positions (counted from the top of the original deck) where the good cards must be placed, in ascending order, one per line. With those placements, Bessie receives every good card when the deck is dealt out.

Hint

Consider the case N=3N = 3, K=9K = 9, P=2P = 2. Each time Bessie deals one card she moves the top two cards to the bottom of the deck.

Placing the good cards at positions 33, 77, and 88 of the original deck works. The deck is dealt as follows (every number is a card's position in the original deck):

StepDeck (top -> bottom)P1P2Bessie
Initial deck1 2 3 4 5 6 7 8 9- - -- - -- - -
Deal top card [1] to Player 12 3 4 5 6 7 8 91 - -- - -- - -
Move top card to bottom (1 of 2)3 4 5 6 7 8 9 21 - -- - -- - -
Move top card to bottom (2 of 2)4 5 6 7 8 9 2 31 - -- - -- - -
Deal top card [4] to Player 25 6 7 8 9 2 31 - -4 - -- - -
Move top card to bottom (1 of 2)6 7 8 9 2 3 51 - -4 - -- - -
Move top card to bottom (2 of 2)7 8 9 2 3 5 61 - -4 - -- - -
Deal top card [7] to Bessie8 9 2 3 5 61 - -4 - -7 - -
Move top card to bottom (1 of 2)9 2 3 5 6 81 - -4 - -7 - -
Move top card to bottom (2 of 2)2 3 5 6 8 91 - -4 - -7 - -
Deal top card [2] to Player 13 5 6 8 91 2 -4 - -7 - -
Move top card to bottom (1 of 2)5 6 8 9 31 2 -4 - -7 - -
Move top card to bottom (2 of 2)6 8 9 3 51 2 -4 - -7 - -
Deal top card [6] to Player 28 9 3 51 2 -4 6 -7 - -
Move top card to bottom (1 of 2)9 3 5 81 2 -4 6 -7 - -
Move top card to bottom (2 of 2)3 5 8 91 2 -4 6 -7 - -
Deal top card [3] to Bessie5 8 91 2 -4 6 -7 3 -
Move top card to bottom (1 of 2)8 9 51 2 -4 6 -7 3 -
Move top card to bottom (2 of 2)9 5 81 2 -4 6 -7 3 -
Deal top card [9] to Player 15 81 2 94 6 -7 3 -
Move top card to bottom (1 of 2)8 51 2 94 6 -7 3 -
Move top card to bottom (2 of 2)5 81 2 94 6 -7 3 -
Deal top card [5] to Player 281 2 94 6 57 3 -
Move top card to bottom (1 of 2)81 2 94 6 57 3 -
Move top card to bottom (2 of 2)81 2 94 6 57 3 -
Deal top card [8] to Bessie(empty)1 2 94 6 57 3 8

Bessie ends up holding the good cards that were placed at positions 33, 77, and 88.

Examples1

  1. Example 1

    Input
    3 9 2
    
    Expected output
    3
    7
    8