Змагання ельфів#10266

Змагання ельфів

1 секунда

256 мегабайтів

Легка

Дідусик Морозик влаштує змагання по футболу серед ельфів.

Всього у розпорядженні Дідусика $2^{n}$ 2^n ельфів, пронумерованих цілими числами від $1$ до $2^{n}$ 2^n. Морозик визначив, що у зустрічі двох ельфів завжди перемагає ельф з більшим номером.

Змагання буде проведено за наступними правилами. Всі ельфи вишикуються у шеренгу, після чого перший ельф з шеренги зустрінеться у поєдинку з другим ельфом з шеренги, третій з четвертим, п'ятий з шостим і так далі... У кожній парі той ельф, що програє зустріч, буде вилучений з турніру, а всі інші знову утворять шеренгу зімкнувши стрій. Наприклад, якщо шеренга складається з ельфів $(4, 2, 3, 1)$ (4,2,3,1) (тут числа — номери ельфів), то ельфи з номерами $2$ та $1$ будуть вилучені з турніру, а ельфи-переможці утворять шеренгу $(4, 3)$ . Така операція буде проведена $n$ разів, після чого у шеренгі залишиться лише один ельф який і буде визначений переможцем.

Ви — фанат ельфа з номером $k$ , якому сьогодні виповнилося $m$ рочків. У якості подарунка Вам потрібно знайти таку початкову шеренгу ельфів, що ельф з номером $k$ переможе у рівно $m$ зустрічах турніру.

Вхідні дані

Перший рядок містить три цілі числа $n$ , $k$ та $m$ ( $1 \leq n \leq 15$ 1\le n\le 15, $1 \leq k \leq 2^{n}$ 1\le k\le 2^n, $0 \leq m \leq n$ 0\le m\le n).

Вихідні дані

Якщо необхідної початкової шеренги не існує, то виведіть одне ціле число $- 1$ .

Інакше, виведіть $2^{n}$ 2^n чисел — номери ельфів у шуканій шеренгі.

Якщо існує кілька правильних відповідей, дозволяється вивести будь-яку з них.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У першому прикладі шеренга ельфів буде модифікуватися наступним чином: $(1, 4, 2, 3)$ (1,4,2,3) $\to$ $(4, 3)$ $\to$ $(4)$ .

У другому прикладі шеренга ельфів буде модифікуватися наступним чином: $(4, 1, 8, 2, 3, 5, 6, 7)$ (4,1,8,2,3,5,6,7) $\to$ $(4, 8, 5, 7)$ (4,8,5,7) $\to$ $(8, 7)$ $\to$ $(8)$ .