Это сложная версия задачи. Единственное отличие — в этой версии задачи \(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\).
Можно показать, что при заданных ограничениях ответ всегда существует.
Выходные данные
Для каждого набора входных данных выведите \(k\) положительных целых чисел \(a_1, a_2, \ldots, a_k\), удовлетворяющих необходимым условиям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
6 4
9 5
|
1 2 2 1
1 3 3 1 1
|