자릿수 합이 같은 등차수열의 항

모든 자연수 $n$에 대해 정의된 무한 등차수열 $A(n) = Cn + D$가 있다. $A(n_1), A(n_2), \dots, A(n_M)$을 $B$진법으로 적었을 때 자릿수의 합이 모두 같도록, $10^{15}$ 이하인 서로 다른 자연수 $n_1, n_2, \dots, n_M$을 찾아라.

양의 정수 $N$의 $B$진법 표기는 하나뿐이다. 각 $i$에 대해 $0 \le x_i < B$이고 $x_k B^k + x_{k-1} B^{k-1} + \dots + x_1 B + x_0 = N$을 만족하는 자릿수 열 $x_k x_{k-1} \dots x_1 x_0$이 그것이며, 자릿수의 합은 $x_k + \dots + x_0$이다.

조건을 만족하는 답은 보통 여러 가지다. 그중 하나를 다음 규칙으로 정한다. 자연수 $n$에 대해 $A(n)$의 $B$진법 자릿수 합을 $f(n)$이라고 하자. $n = 1, 2, 3, \dots$ 순서로 $f(n)$을 계산하면서 각 값이 나온 횟수를 센다. 어떤 값의 횟수가 처음으로 $M$이 되는 순간 멈추고, 그 값을 $s$라고 하자. 그때까지 살펴본 $n$ 가운데 $f(n) = s$인 것이 정확히 $M$개이고, 이 $M$개가 답이다.

첫째 줄에 정수 $C$, $D$, $B$, $M$이 공백으로 구분되어 주어진다. ($1 \le C, D \le 10000$, $2 \le B \le 5000$, $1 \le M \le 250000$)

$n$이 $1$부터 $10^7$까지 가는 동안 어떤 자릿수 합의 횟수가 $M$에 도달하도록 입력이 주어진다.

첫째 줄에 위 규칙으로 정해진 $M$개의 수를 증가하는 순서로 공백 하나씩으로 구분해 출력한다.

$A(n_i)$가 아니라 $n_i$를 출력한다. 출력하는 수는 모두 $10^{15}$ 이하다.

첫 번째 예제에서 $A(2) = 5 \times 2 + 3 = 13$이고 $A(5) = 5 \times 5 + 3 = 28$이다. $13$을 2진법으로 적으면 $1101$, $28$을 적으면 $11100$이라서 자릿수 합이 둘 다 $3$이다. 값 $3$의 횟수가 $n = 5$에서 처음으로 $2$가 되고, 그보다 먼저 $2$에 도달하는 값은 없다.

두 번째 예제에서 $A(2) = 5$, $A(11) = 23$, $A(20) = 41$이다. 셋 다 10진법 자릿수 합이 $5$이고, $n = 20$보다 먼저 횟수가 $3$이 되는 값은 없다.