H. Игрушки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Вероники огромное количество игрушек – целых $$$n$$$ штук. Вероника решила определить, какие игрушки ей нравятся больше всего. Для этого она выставила все $$$n$$$ игрушек в один ряд. Первой игрушке она дала значение равное $$$a_1$$$. Каждой следующей игрушке она дала значение по следующему правилу:

$$$a_i = (a_{i-1}*k)\%p$$$.

где $$$k$$$, $$$p$$$  — параметры красоты, %  — взятие остатка. Вероника хочет из всего набора своих игрушек узнать пять самых больших значений, помогите ей в этом нелегком деле.

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

В единственной строке заданы четыре целых числа $$$n$$$, $$$a_1$$$, $$$k$$$, $$$p$$$ $$$(5\leq n\leq 2 \cdot 10^7, 1\leq a_1, k, p\leq 10^9)$$$  — количество игрушек, значение первой игрушки и параметры зависимости.

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

Выведите в порядке возрастания пять самых больших значения среди игрушек Вероники, разделяя их пробелом.

Примеры
Входные данные
5 1 2 100
Выходные данные
1 2 4 8 16
Входные данные
10 10 3 1000
Выходные данные
430 610 810 830 870