\(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\). Вам нужно по этим трем числам восстановить, какое место заняла какая команда (если это вообще возможно).
Выходные данные
Если распределения команд по местам, удовлетворяющего всем требованиям, не существует, выведите \(-1\).
Иначе выведите \(2^k\) чисел, \(i\)-е из которых должно быть равно \(p_i\) (месту, занятому \(i\)-й командой). Обратите внимание: ваш ответ должен быть корректным вариантом результатов турнира, проводимого по описанным правилам; кроме того, структура турнира является фиксированной (например, команды \(1\) и \(2\) всегда играют между собой в первой фазе турнира). Если существует несколько способов восстановить места, занятые командами, выведите любой из них.
Примечание
Турнир из первого примера описан на картинке в условии.
Для третьего примера, если выбрать расстановку команд по местам \([1, 2, 3, 3]\) (команда \(1\) занимает место \(1\), команда \(2\) занимает место \(2\), команды \(3\) и \(4\) занимают место \(3\)), можно получить хэш турнира, равный \(7020100\) (при \(A = 100\)). Однако такое распределение мест не может быть результатом турнира, потому что команды \(1\) и \(2\) обязательно должны играть друг с другом в полуфинале, поэтому они не могут занять два первых места.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1337 75275197
|
5 3 5 2 1 5 5 3
|
|
2
|
2 100 5040100
|
1 3 3 2
|
|
3
|
2 100 7020100
|
-1
|