F. Преобразование произведения
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим массив A с N элементами, все из которых равны a.

Определим преобразование произведение как одновременное обновление элементов массива Ai = Ai·Ai + 1, которое умножает каждый элементы на элемент справа от него для , а последний элемент AN остаётся неизменным. Например, если мы начнём с массива A с a = 2 и N = 4, после первого преобразования произведения A = [4,  4,  4,  2], а после двух A = [16,  16,  8,  2].

Ваша простая задача — найти массив A после M преобразований произведения. Так как числа могут стать очень большими, выведите ответ по модулю Q.

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

Единственная строка содержит четыре целых числа N, M, a, Q (7 ≤ Q ≤ 109 + 123, 2 ≤ a ≤ 106 + 123, , простое), где  — мультипликативный порядок числа a по модулю Q, см. пояснения.

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

Выведите массив A слева направо, разделённый пробелами.

Пример
Входные данные
2 2 2 7
Выходные данные
1 2
Примечание

Мультипликативный порядок числа a по модулю Q  — это наименьшее положительное целое число x такое, что ax mod Q = 1. Например, .