H. Toys
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Veronika has a huge number of toys – as many as $$$n$$$ pieces. Veronica decided to determine which toys she liked the most. To do this, she put all $$$n$$$ toys in one row. She gave the first toy a value equal to $$$a_1$$$. She gave each next toy a value according to the following rule:

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

where $$$k$$$, $$$p$$$  — beauty parameters. Veronica wants to find out the five largest values from the whole set of her toys. Help her in this difficult task.

Input

A single line contains four integers $$$n$$$, $$$a_1$$$, $$$k$$$, $$$p$$$ $$$(5\leq n\leq 2 \cdot 10^7, 1\leq a_1, k, p\leq 10^9)$$$  — the number of toys, the value of the first toy and the dependency parameters.

Output

Print the five largest values among Veronica's toys, separated by space, in ascending order.

Examples
Input
5 1 2 100
Output
1 2 4 8 16
Input
10 10 3 1000
Output
430 610 810 830 870