题目内容

一位探险家在古老遗迹中找到了 $n$ 个宝箱，每个宝箱里装有 $1$ 到 $6$ 颗宝石。他统计出所有宝箱的宝石总数为 $S$。

随后，探险家决定带走宝石数量最多的 $k$ 个宝箱（若出现并列，他可以任选其中的 $k$ 个），将剩余的 $n-k$ 个宝箱留给同伴，这些剩余宝箱的宝石总数为 $R$。

现在已知四个整数 $n,k,S,R$，请你帮助探险家重构一组可能的原始宝石序列 $v_1,v_2,\dots,v_n$，要求满足：

• 每个 $v_i$ 均为整数且 $1 \le v_i \le 6$；
• $\sum_{i=1}^n v_i = S$；
• 从中选出 $k$ 个最大值（即最大的 $k$ 个元素）后，剩下 $n-k$ 个元素的和恰好为 $R$。

如果不存在符合条件的序列，请指出无解。

约束条件

• 宝箱总数 $n$ 满足 $2 \le n \le 200\,000$；
• 取走的宝箱数 $k$ 满足 $1 \le k < n$；
• 总和 $S$ 与剩余和 $R$ 满足 $1 \le R < S \le 1.2 \times 10^6$。

输入描述

输入只有一行，包含四个整数 $n$, $k$, $S$, $R$，以空格分隔。数据保证满足上述约束范围。

输出描述

若存在合法方案，输出一行 $n$ 个整数，表示一组合法的宝箱宝石序列，整数之间用空格分隔；否则输出 -1。

样例1

输入

5 2 20 10

输出

4 4 2 6 4

说明

宝箱总数 $n=5$，取走 $k=2$，总宝石数 $S=20$，剩余宝石数 $R=10$。剩余宝箱数 $m=n-k=3$，取走的宝石数和 $T=S-R=10$。

枚举阈值 $c$：

• 当 $c=4$ 时，剩余和 $R=10$ 满足 $3 \le 10 \le 3 \times 4 = 12$，取走和 $T=10$ 满足 $2 \times 4=8 \le 10 \le 6 \times 2=12$，因此 $c=4$ 可行。

构造剩余 $3$ 个宝箱（范围 $[1,4]$）：初始每个为 $1$，剩余调节量 $10-3=7$。依次分配最大值 $\min(7,3)=3$，得 4；剩余 $4$，再分配 $\min(4,3)=3$，得 4；最后剩余 $1$，分配 $1$ 得 2。剩余序列为 4 4 2。

构造取走的 $2$ 个宝箱（范围 $[4,6]$）：初始每个为 $c=4$，和为 $8$，剩余调节量 $10-8=2$。先分配 $\min(2,2)=2$，得 6；再分配 $0$ 得 4。取走序列为 6 4。

合并得到完整序列 4 4 2 6 4。前 $2$ 大的元素为 $6$ 和 $4$，剩余元素和 $4+4+2=10$，且总和为 $20$，均满足要求。

样例2

输入

3 1 10 8

输出

-1

说明

宝箱总数 $n=3$，取走 $k=1$，总宝石数 $S=10$，剩余宝石数 $R=8$。剩余宝箱数 $m=2$，取走的宝石数和 $T=S-R=2$。

枚举阈值 $c$：

• 剩余和 $R=8$ 要求 $m \le R \le m \times c$，即 $2 \le 8 \le 2c$，解得 $c \ge 4$。
• 取走和 $T=2$ 要求 $k \times c \le T \le 6k$，即 $c \le 2 \le 6$，解得 $c \le 2$。

不存在同时满足 $c \ge 4$ 和 $c \le 2$ 的整数 $c$，因此无解，输出 -1。

样例3

输入

5 3 30 12

输出

6 6 6 6 6

说明

宝箱总数 $n=5$，取走 $k=3$，总宝石数 $S=30$，剩余宝石数 $R=12$。剩余宝箱数 $m=2$，取走的宝石数和 $T=18$。

枚举阈值 $c$：

• 当 $c=6$ 时，剩余和满足 $2 \le 12 \le 2 \times 6=12$，取走和满足 $3 \times 6=18 \le 18 \le 6 \times 3=18$，边界刚好成立。

构造剩余 $2$ 个宝箱（范围 $[1,6]$）：初始各为 $1$，剩余调节量 $12-2=10$。依次分配 $\min(10,5)=5$，得 6，再分配 $5$，得 6，得到 6 6。取走的 $3$ 个宝箱（范围 $[6,6]$）：每个直接为 $6$，得到 6 6 6。

完整序列为全 6。最大的 $3$ 个均为 $6$，剩余 $2$ 个的和为 $12$，满足边界条件。

样例4

输入

4 2 12 5

输出

3 2 4 3

说明

宝箱总数 $n=4$，取走 $k=2$，总宝石数 $S=12$，剩余宝石数 $R=5$。剩余宝箱数 $m=2$，取走的宝石数和 $T=7$。

枚举阈值 $c$：

• $c=3$ 时，剩余和 $5$ 满足 $2 \le 5 \le 2 \times 3=6$，取走和 $7$ 满足 $2 \times 3=6 \le 7 \le 12$，可行。

剩余 $2$ 个宝箱（范围 $[1,3]$）：初始各 $1$，调节量 $5-2=3$。先分配 $\min(3,2)=2$ 得 3，再分配 $1$ 得 2，序列为 3 2。取走 $2$ 个宝箱（范围 $[3,6]$）：初始各 $3$ 和为 $6$，调节量 $7-6=1$。第一个分配 $1$ 得 4，第二个得 3，序列为 4 3。

完整序列为 3 2 4 3。最大的 $2$ 个为 $4$ 和 $3$，剩余和为 $3+2=5$，总和为 $12$，符合要求。