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} + \dots + x_1 B + x_0 = N~ is satisfied. The sum of digits is given with ~x_k + \dots + x_0~.

Input Specification

The first line of input contains four integers ~C~, ~D~, ~B~ and ~M~ ~(1 \le C, D \le 10\,000, 2 \le B \le 5\,000, 1 \le M \le 250\,000)~.

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~.