ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2004 Round 1

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. ACM Diagnostics

Time limit: 0.5 second
Memory limit: 64 MB
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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1310. ACM Diagnostics