Maps
The deck consists of an even number of cards, numbered consecutively from 1 to 2n, where n is a natural number. The following steps are performed on the deck:
1. The deck is split into two equal parts. The first part contains cards from the odd positions, and the second part contains cards from the even positions:
(1, 2, … , 2n) (1, 3, 5, … , 2n – 1) + (2, 4, … , 2n)
2. From each part, the card at position 1 + [an/b] is removed, where 0 ≤ a < b ≤ 1000. For instance, if a = 0 and b = 1, the first card is removed:
(1, 3, 5, … , 2n – 1) (3, 5, 7, ... , 2n – 1)
(2, 4, 6, … , 2n) (4, 6, 8, … , 2n)
3. The second part is placed on top of the first:
(3, 5, 7, ... , 2n – 1) + (4, 6, 8, … , 2n) (3, 5, 7, … , 2n – 1, 4, 6, 8, … , 2n)
These steps are repeated until only 2 cards remain in the deck. For example, if a = 1, b = 2, and the initial number of cards is 5, the process is as follows:
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) (1, 3, 5, 7, 9) + (2, 4, 6, 8, 10)
(1, 3, 7, 9) + (2, 4, 8, 10) (1, 3, 7, 9, 2, 4, 8, 10) (1, 7, 2, 8) + (3, 9, 4, 10)
(1, 7, 8) + (3, 9, 10) (1, 7, 8, 3, 9, 10) (1, 8, 9) + (7, 3, 10)
(1, 9) + (7, 10) (1, 9, 7, 10) (1, 7) + (9, 10) (1) + (9) (1, 9),
because 1 + [5∙1/2] = 3, 1 + [4∙1/2] = 3, 1 + [3∙1/2 ] = 2, 1 +[2∙1/2] = 2.
Determine the final state of the deck.
Input
The input consists of 3 non-negative integers: n, a, b (2 ≤ n ≤ 500000).
Output
Output the numbers of the two remaining cards, with the number of the bottom card listed first.