题目描述

ARC 国有 $N$ 名国民，所有国民都是竞赛编程的玩家。根据每个人的竞赛编程实力，每位国民被分配了 $1, 2, \ldots, K$ 中的某一个段位。

在 ARC 国进行了一次人口普查，结果显示，段位 $i$ 的国民恰好有 $A_i$ 人。国王希望将这份统计数据以更易理解的方式展示，于是决定以 $M$ 人的村庄为例，尽量保持各段位人数比例不变。

请你为 $M$ 人的村庄合理分配每个段位 $i$ 的村民人数 $B_i$，使得 $\max_i\left|\frac{B_i}{M} - \frac{A_i}{N}\right|$ 尽可能小。需要满足以下条件：

• 每个 $B_i$ 是非负整数，且 $\sum_{i=1}^K B_i = M$。

请输出任意一种满足条件的 $B = (B_1, B_2, \ldots, B_K)$。

输入格式

输入以如下格式从标准输入读入：

$K$ $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_K$

输出格式

请输出满足条件的整数序列 $B$，各元素用空格隔开，输出一行：

$B_1$ $B_2$ $\ldots$ $B_K$

如果存在多组满足条件的解，输出任意一组均可。

样例 1

输入

3 7 20
1 2 4

输出

3 6 11

样例 2

输入

3 3 100
1 1 1

输出

34 33 33

样例 3

输入

6 10006 10
10000 3 2 1 0 0

输出

10 0 0 0 0 0

样例 4

输入

7 78314 1000
53515 10620 7271 3817 1910 956 225

输出

683 136 93 49 24 12 3

说明/提示

约束条件

• $1 \leq K \leq 10^5$
• $1 \leq N, M \leq 10^9$
• 每个 $A_i$ 是非负整数，且 $\sum_{i=1}^K A_i = N$

样例解释 1

对于该输出，$\max\_i\left|\frac{B\_i}{M} - \frac{A\_i}{N}\right| = \max\left(\left|\frac{3}{20}-\frac{1}{7}\right|, \left|\frac{6}{20}-\frac{2}{7}\right|, \left|\frac{11}{20}-\frac{4}{7}\right|\right) = \max\left(\frac{1}{140}, \frac{1}{70}, \frac{3}{140}\right) = \frac{3}{140}$。

样例解释 2

需要注意的是，$B_1 = B_2 = B_3 = 33$ 不满足 $B_1 + B_2 + B_3 = M = 100$ 的条件。在本例中，34 33 33、33 34 33 或 33 33 34 等输出都是正确答案。

由 ChatGPT 4.1 翻译