[AdditionalFile5237.zip](file://AdditionalFile5237.zip?type=additional_file)

#5237. 「UOI 2020 Stage 4 Day1」缩小数组

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2020 Stage 4 Day1 T4. Зменшення масиву

给定一个包含 $n$ 个整数的数组 $a$。在一次操作中，你可以选择一个位置 $i$ $(1 \leq i \leq n)$，将 $a_i$ 减少 $k$，同时将数组中所有其他元素 $a_j$ $(1 \leq j \leq n, i \neq j)$ 增加 $t$。

找出使数组中所有元素都小于或等于零（即非正数）所需的最小操作次数，或者报告这是不可能的。

输入格式

第一行包含三个整数 $n, k, t$ $(1 \leq n \leq 10^{6}, 0 \leq k, t \leq 10^{9})$，分别表示数组长度和操作参数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-10^{18} \leq a_i \leq 10^{9})$，表示数组元素的初始值。

输出格式

输出一个整数 $c$，表示使数组所有元素小于或等于零所需的最小操作次数。如果无法实现，则输出 $-1$。

如果可以实现，则输出 $n$ 个整数 $cnt_i$ $(1 \leq i \leq n)$，表示对编号为 $i$ 的元素执行的操作次数。请注意，必须满足等式 $\sum\limits_{i=1}^n cnt_i = c$。

样例 1

输入

4 10 1
2 5 9 -4

输出

4
1 1 2 0

样例 2

输入

5 1 100
-1000 -1000 10 -1000 -1000

输出

10
0 0 10 0 0

样例 3

输入

2 1 1
1 0

输出

-1

数据范围与提示

详细子任务附加限制及分值如下表所示：