Kotrljanje

Κανείς δεν έρχεται πλέον στις ώρες γραφείου του Vlatko. Θυμωμένος, εξαγριομένος και δυσαρεστημένος, η εκδίκηση του Βλάτκο είναι μια βολική δουλειά για την COCI:

Σας δίνεται μια άπειρη αριθμητική ακολουθία ​A(n) = ​Cn + D​, που ορίζεται για όλους τους φυσικούς αριθμούς n. Θέλουμε να βρούμε μια ακολουθία M διακριτών φυσικών αριθμών ​n₁,​ n₂,​ ..., n_M μικρότερη ή ίση με 10¹⁵ έτσι ώστε τα αντίστοιχα μέλη της ακολουθίας A(n₁), A(n₂), ... , A(n_M)​ έχουν όλα το ίδιο άθροισμα ψηφίων στη βάση Β.​

Σημείωση: Κάθε θετικός ακέραιος N μπορεί να γραφτεί στη βάση Β ως εξής: Δημιούργηστε μια συμβολοσειρά ~ x_kx_{k-1}\dots x_1x_0 ~ με 0 ≤ ~x_i~ ≤B για κάθε i, και η εξίσωση ~x_k*B^k + x_{k-1}*B^{k-1} + \dots + x_1*B +x_0 ~ = N ικανοποιείται. Το σύνολο των ψηφίων δίνεται από x_k + ... + x₀.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει τέσσερις ακέραιους αριθμούς ​C​, ​D​, ​B​ και ​M​ (1 ≤ C,​D ≤ 10.000, 2 ≤ B ≤ 5.000​, ​1 ≤ M ≤ 250.000).

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τους απαιτούμενους αριθμούς, διαχωρισμένους με κενά, με αυθαίρετη σειρά.

Σημείωση: πρέπει να δώσετε τους αριθμούς ​~n_i~,​ όχι τους αριθμούς ~A(n_i)~. Όλοι οι αριθμοί στην έξοδο πρέπει να είναι μικρότεροι ή ίσοι με ~10^{15}~. Τα δεδομένα εισόδου θα είναι τέτοια ώστε να υπάρχει μια λύση που να πληρεί τις δεδομένες συνθήκες.

Παραδείγματα

input

5 3 2 2

output

2 5

Επεξήγηση του 1ου παραδείγματος:

Μία από τις πιθανές ακολουθίες είναι η ακολουθία στην έξοδο. Τα αντίστοιχα μέλη της αριθμητικής ακολουθίας είναι 5 2 + 3 = 13 και 5 5 + 3 = 28. Η μορφή του αριθμού 13 με βάση 2 είναι 1101, ενώ η μορφή του αριθμού 28 με βάση 2 είναι 11100. Το άθροισμα των ψηφίων στα 2 φορμάτ είναι ίσο με 3.

input

2 1 10 3

output

2 20 200

Επεξήγηση του 2ου παραδείγματος:

Τα αντίστοιχα μέλη της ακολουθίας είναι ~2 * 2 + 1 = 5, 2 * 20 + 1 = 41 ~ και ~2 * 200 + 1 = 401~. Καθένα από τα ψηφία των αριθμών, γραμμένο στη βάση 10, αθροίζει μέχρι το 5.