A1370 | [COCI-2017_2018-contest6]#4 Kotrljanje

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 find a sequence of M distinct natural numbers n1, n2, ..., nM less than or equal to 10^15 such that the corresponding members of sequence A(n1), A(n2), ..., A(nM) 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 xkxk-
1...x1x0, where 0 ≤ xi < B for each i, and the equation xkBk + xk-1Bk-1 + ... + x1B + x0 =N is satisfied. The sum of digits is given with xk + ... + x
0.

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

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^1
5.
The input data will be such that a solution that meets the given conditions exists.