这是问题的困难版本。唯一的区别是在这个版本中 $$$3 \le k \le n$$$。
给你一个正整数$$$n$$$。找到 $$$k$$$ 正整数 $$$a_1, a_2, \ldots, a_k$$$,这样:
- $$$a_1 + a_2 + \ldots + a_k = n$$$
- $$$LCM(a_1, a_2, \ldots, a_k) \le \frac{n}{2}$$$
这里 $$$LCM$$$ 是数字 $$$a_1, a_2, \ldots, a_k$$$ 的最小公倍数。
我们可以证明,对于给定的约束,答案总是存在。
输入
第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。
每个测试用例的唯一行包含两个整数 $$$n$$$, $$$k$$$ ($$$3 \le n \le 10^9$$$, $$$3 \le k \le n$$$)。
保证所有测试用例的$$$k$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,打印 $$$k$$$ 正整数 $$$a_1, a_2, \ldots, a_k$$$,满足所有条件。
示例
输入 #1
2 6 4 9 5
输出 #1
1 2 2 1 1 3 3 1 1