C2. k-НОК (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие  — в этой версии задачи $$$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$$$, удовлетворяющих необходимым условиям.

Пример
Входные данные
2
6 4
9 5
Выходные данные
1 2 2 1 
1 3 3 1 1