E. Восстановление турнирной таблицы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$2^k$$$ команд участвуют в плей-офф турнире. Турнир состоит из $$$2^k - 1$$$ игры. Они проводятся следующим образом: во-первых, команды делятся на пары: команда $$$1$$$ играет против команды $$$2$$$, команда $$$3$$$ играет против команды $$$4$$$ (именно в таком порядке) и так далее (таким образом, в этой фазе будет сыграно $$$2^{k-1}$$$ игры). Когда команда проигрывает игру, она выбывает, и каждая игра приводит к выбыванию одной команды (нет ничьих). После этого остается $$$2^{k-1}$$$ команд. Если остается только одна команда, она объявляется чемпионом; в противном случае играется еще $$$2^{k-2}$$$ игр: в первой из них победитель игры «$$$1$$$ против $$$2$$$» играет против победителя игры «$$$3$$$ против $$$4$$$», затем победитель игры «$$$5$$$ против $$$6$$$» играет против победителя игры «$$$7$$$ против $$$8$$$» и так далее. Этот процесс повторяется до тех пор, пока не останется только одна команда.

Место команды в турнире зависит от того, в какой фазе турнира она выбыла:

  • команда-победитель турнира занимает место $$$1$$$;
  • команда, выбывшая в финале, занимает место $$$2$$$;
  • обе команды, выбывшие в полуфинале, занимают место $$$3$$$;
  • все команды, выбывшие в четвертьфинале, занимают место $$$5$$$;
  • все команды, выбывшие в 1/8 финала, занимают место $$$9$$$, и так далее.

Например, на этой картинке показан возможный ход турнира при $$$k = 3$$$, а также итоговые места команд при таком ходе турнира:

После окончания турнира, который проходил по этим правилам, его результаты были закодированы следующим образом. Пусть $$$p_i$$$ — место, которое заняла $$$i$$$-я команда. Хэш турнира $$$h$$$ считается по формуле $$$h = (\sum \limits_{i=1}^{2^k} i \cdot A^{p_i}) \bmod 998244353$$$, где $$$A$$$ — некоторое заданное целое число.

К сожалению, из-за сбоя системы почти вся информация о прошедшем турнире была утеряна. Остались только значения $$$k$$$, $$$A$$$ и $$$h$$$. Вам нужно по этим трем числам восстановить, какое место заняла какая команда (если это вообще возможно).

Входные данные

В единственной строке заданы три числа $$$k$$$, $$$A$$$ и $$$h$$$ ($$$1 \le k \le 5$$$; $$$100 \le A \le 10^8$$$; $$$0 \le h \le 998244352$$$).

Выходные данные

Если распределения команд по местам, удовлетворяющего всем требованиям, не существует, выведите $$$-1$$$.

Иначе выведите $$$2^k$$$ чисел, $$$i$$$-е из которых должно быть равно $$$p_i$$$ (месту, занятому $$$i$$$-й командой). Обратите внимание: ваш ответ должен быть корректным вариантом результатов турнира, проводимого по описанным правилам; кроме того, структура турнира является фиксированной (например, команды $$$1$$$ и $$$2$$$ всегда играют между собой в первой фазе турнира). Если существует несколько способов восстановить места, занятые командами, выведите любой из них.

Примеры
Входные данные
3 1337 75275197
Выходные данные
5 3 5 2 1 5 5 3 
Входные данные
2 100 5040100
Выходные данные
1 3 3 2 
Входные данные
2 100 7020100
Выходные данные
-1
Примечание

Турнир из первого примера описан на картинке в условии.

Для третьего примера, если выбрать расстановку команд по местам $$$[1, 2, 3, 3]$$$ (команда $$$1$$$ занимает место $$$1$$$, команда $$$2$$$ занимает место $$$2$$$, команды $$$3$$$ и $$$4$$$ занимают место $$$3$$$), можно получить хэш турнира, равный $$$7020100$$$ (при $$$A = 100$$$). Однако такое распределение мест не может быть результатом турнира, потому что команды $$$1$$$ и $$$2$$$ обязательно должны играть друг с другом в полуфинале, поэтому они не могут занять два первых места.