本题是一个典型的可行性判定 + 贪心构造问题。 记每个元素必须在区间 [l,r] 内,数组长度为 n,目标总和为 m。
可行性判定:数组元素之和的最小/最大可能值分别为
Smin=n⋅l,Smax=n⋅r.Tk 从小就对数字非常感兴趣,Tk 希望构造一个长度为 n 的整数数组 a,满足所有元素的和为 m ,且每个元素都在区间 [l,r] 之间。
然而,Tk 并不会具体构造,于是找到了聪明的你,需要你输出任意一种满足条件的数组如果无解,则输出 r+1 。
每个测试文件均包含多组测试数据。
第一行输入一个整数 T(1≤T≤104),代表测试组数;
此后每组测试教据描述如下:
在一行上输入四个整数 n,m,l,r(1≦n≦2×105;−109≦m≦109;−109≦l≦r≦109) 。
此外,保证单个测试文件中所有 n 之和不超过 2×105 。
对于每一组测试数据,新起一行,输出 n 个整数表示满足条件的数组;如果无解,输出 r+1 。
输入
2
3 6 1 3
2 100 0 10
输出
2 2 2
11