No tags yet

No tag edit access

time limit per test: 0.5 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: standard

output: standard

N robbers have robbed the bank. As the result of their crime they chanced to get M golden coins. Before the robbery the band has made an agreement that after the robbery i-th gangster would get X_{i}/Y of all money gained. However, it turned out that M may be not divisible by Y.

The problem which now should be solved by robbers is what to do with the coins. They would like to share them fairly. Let us suppose that i-th robber would get K_{i} coins. In this case unfairness of this fact is |X_{i}/Y-K_{i}/M|. The total unfairness is the sum of all particular unfairnesses. Your task as the leader of the gang is to spread money among robbers in such a way that the total unfairness is minimized.

The problem which now should be solved by robbers is what to do with the coins. They would like to share them fairly. Let us suppose that i-th robber would get K

The first line of the input file contains numbers N, M and Y (1 ≤ N ≤ 1000, 1 ≤ M, Y ≤ 10000). N integer numbers follow - X_{i} (1 ≤ X_{i} ≤ 10000, sum of all X_{i} is Y).

Output N integer numbers — K_{i} (sum of all K_{i} must be M), so that the total unfairness is minimal.

Input

3 10 4

1 1 2

1 1 2

Output

2 3 5

Author: | Andrew Stankevich |

Resource: | Petrozavodsk Summer Trainings 2003 |

Date: | 2003-08-23 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/24/2020 01:10:04 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|