Vla-tko, Vla-tko, Vla-tko！

再也没有人来参加 Vlatko 的答疑时间了。愤怒、暴躁又心怀不满的 Vlatko 决定通过为 COCI 出一道题来进行他的复仇：

给你一个定义在所有正整数 $n$ 上的无限等差数列 $A(n) = Cn + D$。我们希望找到一个由 $M$ 个互不相同的正整数 $n_1, n_2, \dots, n_M$ 组成的序列，满足 $n_i \le 10^{15}$，且等差数列中对应的项 $A(n_1), A(n_2), \dots, A(n_M)$ 在 $B$ 进制下的数位和全部相同。

请注意：每个正整数 $N$ 都可以用 $B$ 进制表示为唯一的字符串 $x_k x_{k-1} \dots x_1 x_0$，其中对于每个 $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 + \dots + x_0$。

输入格式

第一行包含四个整数 $C, D, B$ 和 $M$（$1 \le C, D \le 10000$，$2 \le B \le 5000$，$1 \le M \le 250000$）。

输出格式

输出的第一行也是唯一的一行应当包含所求的 $M$ 个正整数，以空格分隔，顺序可以任意。

请注意：你必须输出数字 $n_i$，而不是数字 $A(n_i)$。输出中的所有数字都必须小于或等于 $10^{15}$。

输入数据保证存在满足给定条件的解。

样例

输入样例 1

5 3 2 2

输出样例 1

2 5

输入样例 2

2 1 10 3

输出样例 2

2 20 200

说明

在第一个样例中，输出的序列是可能的一种解。等差数列中对应的项为 $5 \times 2 + 3 = 13$ 和 $5 \times 5 + 3 = 28$。数字 13 在二进制下的表示为 1101，而数字 28 在二进制下的表示为 11100。它们在二进制下的数位和都等于 3。

在第二个样例中，序列对应的项为 $2 \times 2 + 1 = 5$，$2 \times 20 + 1 = 41$ 和 $2 \times 200 + 1 = 401$。这些数字在十进制下的数位和都等于 5。