← 返回题目列表

Codeforces · 1497/C2

C2. k-LCM(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。唯一的区别是在这个版本中 $$$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