15498번 - 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 n₁, n₂, ..., n_M less than or equal to 10¹⁵ such that the corresponding members of sequence A(n₁), A(n₂), ..., 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_kx_k-1...x₁x₀ , where 0 ≤ x_i < B for each i, and the equation x_kB^k + x_k-1B^k-1 + ... + x₁B + x₀ = N is satisfied. The sum of digits is given with x_k + ... + x₀.

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¹⁵.

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.