Vla-tko, Vla-tko, Vla-tko!

Nobody comes to Vlatko's office hours anymore. Angered, enraged and disgruntled, Vlatko's revenge is a convenient task for COCI:

You are given an infinite arithmetic sequence $A(n)=Cn+D$, defined for all natural numbers $n$. We want to find a sequence of $M$ distinct natural numbers $n_1,n_2,\dots ,n_M$ less than or equal to ${10}^{15}$ such that the corresponding members of sequence $A(n_1),A(n_2),\dots ,A(n_M)$ all have the same sum of digits in base $B$.

Please note: Every positive integer $N$ can be written in base $B$ as follows: create the unique string $x_k{x}_{k-1}\dots x_1{x}_0$, where $0\le x_i<B$ for each $i$, and the equation $x_k{B}^k+x_{k-1}{B}^{k-1}+\cdots +x_{1}B+x_0=N$ is satisfied. The sum of digits is given with $x_k+\cdots +x_0$.

Input Specification

The first line of input contains four integers $C$, $D$, $B$ and $M$ $(1\le C,D\le 10000,2\le B\le 5000,1\le M\le 250000)$.

Output Specification

The first and only line of output must contain the required numbers, separated by spaces, in an arbitrary order.

Please note: you must output the numbers $n_i$, not numbers $A(n_i)$. All numbers in the output should be less than or equal to ${10}^{15}$.

The input data will be such that a solution that meets the given conditions exists.

Sample Input 1

5 3 2 2

Sample Output 1

2 5

Explanation for Sample Output 1

One of the possible sequences is the sequence in the output. The corresponding members of the arithmetic sequence are $5\times 2+3=13$ and $5\times 5+3=28$. The format of number $13$ in base $2$ is $1101$, whereas the format of number $28$ in base $2$ is $11100$. The sum of digits in both formats is equal to $3$.

Sample Input 2

2 1 10 3

Sample Output 2

2 20 200

Explanation for Sample Output 2

The corresponding members of the sequence are $2\times 2+1=5$, $2\times 20+1=41$, and $2\times 200+1=401$. Each of the numbers' digits, written in base $10$, sum up to $5$.