Competitions

# Implementation: Data Structures

# Throwing cards away

Given an ordered deck of **n** cards numbered from **1** to **n** with card **1** at the top and card **n** at the bottom. The following operation is performed as long as there are at least two cards in the deck: throw away the top card and move the card that is now on the top of the deck to the bottom of the deck. Your task is to find the sequence of discarded cards and the last, remaining card.

#### Input

Each line contains number of cards **n** (**n** ≤ **1000**) in the deck. The last line contains **n** = **0** and should not be processed.

#### Output

For each input number produce two lines. The first line presents the sequence of discarded cards, the second line reports the last remaining card. See the sample for the expected format.

Input example #1

7 10 6 0

Output example #1

Discarded cards: 1, 3, 5, 7, 4, 2 Remaining card: 6 Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8 Remaining card: 4 Discarded cards: 1, 3, 5, 2, 6 Remaining card: 4