A1590.[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.

Clarification of the test cases:
In the first test case, one of the possible sequences is the sequence in the output. The corresponding
members of the arithmetic sequence are 5 * 2 + 3 = 13 and 5 * 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.
In the second test case, the corresponding members of the sequence are 2 * 2 + 1 = 5, 2 * 20 + 1 =
41, and 2 * 200 + 1 = 401. Each of the numbers’ digits, written in base 10, sum up to 5.