题目描述

给定一个包含 $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

样例 1 输出

4
1 1 2 0

样例 2 输入

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

样例 2 输出

10
0 0 10 0 0

样例 3 输入

2 1 1
1 0

样例 3 输出

-1

数据范围

对于所有数据，$1 \leq n \leq 10^6$，$0 \leq k, t \leq 10^9$，$-10^{18} \leq a_i \leq 10^9$。

• 子任务 1（$5$ 分）$t = 0$；
• 子任务 2（$5$ 分）$1 \leq n \leq 300$，$|a_i| \leq 300$，$0 \leq t \leq 10^6$；
• 子任务 3（$10$ 分）$1 \leq n \leq 3000$，$|a_i| \leq 3000$，$0 \leq t \leq 10^6$；
• 子任务 4（$10$ 分）$1 \leq n \leq 10^3$，$a_i \ge 1$，$0 \leq t \leq 10^6$；
• 子任务 5（$5$ 分）$1 \leq n \leq 10^4$，$a_i \ge 1$；
• 子任务 6（$10$ 分）$1 \leq n \leq 10^5$，$a_i \ge 1$；
• 子任务 7（$10$ 分）$a_i \ge 1$；
• 子任务 8（$10$ 分）$1 \leq n \leq 10^3$，$0 \leq t \leq 10^6$；
• 子任务 9（$5$ 分）$1 \leq n \leq 10^4$；
• 子任务 10（$15$ 分）$1 \leq n \leq 10^5$；
• 子任务 11（$15$ 分）无额外限制。