← 返回题目列表

Codeforces · 852/F

F. 产品改造

中文机器翻译题面 查看原题

考虑一个具有 N 个元素的数组 A,所有元素都是相同的整数 a。

将乘积转换定义为同时更新 Ai = Ai·Ai + 1,即将每个元素与其右侧的元素相乘 $$i \in (1, 2,..., N-1)$$,最后一个数字 AN 保持不变。例如,如果我们从 a = 2 且 N = 4 的数组 A 开始,则在一次乘积转换后 A = [4, 4, 4, 2],在两次乘积转换后 A = [16, 16, 8, 2]。

您的简单任务是在 M 次乘积转换后计算数组 A。由于数字可能变得相当大,因此您应该以 Q 为模输出它们。

输入

输入的第一行也是唯一一行包含四个整数 N、M、a、Q(7 ≤ Q ≤ 109 + 123、2 ≤ a ≤ 106 + 123、$$1 \leq M、N < \phi(a, Q) \leq 10^6 + 123$$、$$\phi(a,Q)$$ 是质数),其中$$\phi(a,Q)$$ 是整数 a 模 Q 的乘法阶,定义见注释。

输出

你应该从左到右输出数组A。

示例

输入 #1

2 2 2 7

输出 #1

1 2

注意

数字 a 模 Q $$\phi(a,Q)$$ 的乘法阶是满足 ax mod Q = 1 的最小自然数 x。例如,$$\phi(2,7)=3$$。