2 \(s / 64\) \(MB / 140\) points

V\(la-tk\)o, V\(la-tk\)o, V\(la-tk\)o!

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\) {1}{ }, n {2}{ }, ..., n _{M} less than or equal to

10 ^{15} such that the corresponding members of sequence A(n {1}{ }), A(n {2}{ }), ..., 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\)}{ }...x {1}{ }\(x\) {0}{ }, where 0 ≤ \(x\) {i} < \(B\) for each \(i\) , and the equation \(x\) \(k-1\)">{ }\(B\) ^{k} + x { }\(B\) ^{\(k-1\)} + ... + \(x\) { }\(B + x\) =

\(N\) is satisfied . The sum of digits is given with \(x\) {k}{ } + ... + x {0}{ }.

The first line of input contains four integers \(C\) , \(D\) , \(B\) and \(M\) (1 ≤ C, \(D\) ≤ 10000, \(2 \le B \le 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 ^{15}{ }.
The input data will be such that a solution that meets the given conditions exists.

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Contest 6