Have you ever heard about ACM? May be, may be… It is known to be a new project of computing machinery lab. ACM (Abstract Computation Machine) — it is a new device for quite complex computations. There is only one problem: the pre-production model doesn't work properly. So, the diagnostics is necessary to find out the reasons of the device faults.
There are some necessary facts known about the internal structure of the device. It consists of L independent registers. Each of these registers is able to store the number in the range from 1 to M. Not all registers are used for computations — some of them are used for the proposes of error control. The values of these registers are chosen in such way, that the sum of the values of all registers is divisible by given number K.
The values of all registers of ACM completely define the state of device. So for proposes of diagnostics it is enough to know the values of all these registers. The problem is that developers who created the diagnostics procedure had decided to optimize the presentation of diagnostics information. So instead of simple list of register values the procedure returns the single integer — code of the state.
This code should completely describe the state of device. That's why developers decided to calculate it such way. State of device — is an arbitrary vector of length L, satisfying the demands defined above. And the code of the state is just an index of this vector in the lexicographically increasing list of all possible states. (Note that the first state has index 0). It's easy to understand that such vector completely defines a state of the ACM.
Now the device faults and outputs code of the state. The error code has become useful! Now it is necessary to reconstruct the values of device registers from this code. As you guessed — it is your entry!
Input
The first line of input contains three numbers L, M and K (1 ≤ L ≤ 100; 2 ≤ M ≤ 50; 1 ≤ K ≤ 50)
The second line contains an integer number N — error code, returned by the ACM device.
Output
You are to write the program that outputs the values of device registers, corresponding to the code N. I.e. L integer numbers, separated by spaces.
Sample
input | output |
---|
3 10 4
213 | 9 6 1 |
Problem Author: Idea - Alexander Klepinin, prepared by Alexander Klepinin, Pavel Egorov
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004