eolymp
bolt
Try our new interface for solving problems
Problems

Карты

Карты

Time limit 1 second
Memory limit 122 MiB

Колода состоит из парного количества карт. Карты пронумерованы по­сле­довательными нату­ральными числами от 1 до 2n (для некоторого натурального n) включительно. С колодой производят следующие операции:

1. Сначала колоду делят на две равные части. В первую часть попадают карты, которые стояли на непарных местах, в другую — те карты, что были на парных местах:

(1, 2, … , 2n) (1, 3, 5, … , 2n­ – 1) + (2, 4, … , 2n)

2. Из обеих образованных частей выкидают карту, которая расположена в соответствующей части на месте 1 + [an/b] при 0 a < b1000. На­пример, если a = 0, b = 1, то будет выброшена первая карта:

(1, 3, 5, … , 2n – 1) (3, 5, 7, ... , 2n – 1)

(2, 4, 6, … , 2n) (4, 6, 8, … , 2n)

3. Вторую часть кладут наверх первой:

(3, 5, 7, ... , 2n – 1) + (4, 6, 8, … , 2n) (3, 5, 7, … , 2n – 1, 4, 6, 8, … , 2n)

Действия 1–3 повторяют до тех пор, пока в колоде не останется только 2 карты. Например, если a = 1, b = 2, а начальное количество карт - 5, имеем:

(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),

так как 1 + [5∙1/2] = 3, 1 + [4∙1/2] = 3, 1 + [3∙1/2 ] = 2, 1 +[2∙1/2] = 2.

Определите конечное состояние колоды.

Input data

Содержит 3 неотрицательных целых числа n, a, b (2n500000).

Output data

Вывести два натуральных числа: номера карт, которые останутся. Номер нижней карты следует указать первым.

Examples

Input example #1
5 1 2
Output example #1
1 9