B. Чередующаяся последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$. Массив $$$a$$$ длины $$$n$$$ называется хорошим, если:

  • Для всех $$$1 \le i \lt n$$$, $$$a_i \cdot a_{i+1} \lt 0$$$.
  • Для всех подмассивов$$$^{\text{∗}}$$$ из хотя бы $$$2$$$ элементов, сумма всех элементов подмассива положительна$$$^{\text{†}}$$$.

Кроме того, мы говорим, что хороший массив $$$a$$$ длины $$$n$$$ лучше другого хорошего массива $$$b$$$ длины $$$n$$$, если $$$[|a_1|, |a_2|, \ldots, |a_n|]$$$ лексикографически меньше$$$^{\text{‡}}$$$ чем $$$[|b_1|, |b_2|, \ldots, |b_n|]$$$. Обратите внимание, $$$|z|$$$ обозначает абсолютное значение числа $$$z$$$.

Выведите хороший массив длины $$$n$$$, который лучше, чем любой другой хороший массив длины $$$n$$$.

$$$^{\text{∗}}$$$Массив $$$c$$$ является подмассивом массива $$$d$$$, если $$$c$$$ может быть получен из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

$$$^{\text{†}}$$$Число $$$x$$$ положительно, если $$$x \gt 0$$$.

$$$^{\text{‡}}$$$Последовательность $$$a$$$ лексикографически меньше последовательности $$$b$$$, если и только если выполняется одно из следующего:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$; или
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в последовательности $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.
Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длину вашего массива.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$), элементы вашего массива на новой строке.

Пример
Входные данные
2
2
3
Выходные данные
-1 2
-1 3 -1
Примечание

В первом наборе входных данных, поскольку $$$a_1 \cdot a_2 = -2 \lt 0$$$ и $$$a_1 + a_2 = 1 \gt 0$$$, он удовлетворяет двум условиям. Кроме того, можно показать, что соответствующий $$$b = [1, 2]$$$ является лучше любого другого хорошего массива длины $$$2$$$.