CF2131B Alternating Series

You are given an integer $$$n$$$. Call an array $$$a$$$ of length $$$n$$$ good if: - For all $$$1 \\le i < n$$$, $$$a\_i \\cdot a\_{i+1} < 0$$$ (i.e., the product of adjacent elements is negative). - For all subarrays$$$^{\\text{∗}}$$$ with length at least $$$2$$$, the sum of all elements in the subarray is positive$$$^{\\text{†}}$$$. Additionally, we say a good array $$$a$$$ of length $$$n$$$ is better than another good array $$$b$$$ of length $$$n$$$ if $$$\[|a\_1|, |a\_2|, \\ldots, |a\_n|\]$$$ is lexicographically smaller$$$^{\\text{‡}}$$$ than $$$\[|b\_1|, |b\_2|, \\ldots, |b\_n|\]$$$. Note that $$$|z|$$$ denotes the [absolute value](https://en.wikipedia.org/wiki/Absolute_value) of integer $$$z$$$. Output a good array of length $$$n$$$ such that it is better than every other good array of length $$$n$$$. $$$^{\\text{∗}}$$$An array $$$c$$$ is a subarray of an array $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. $$$^{\\text{†}}$$$An integer $$$x$$$ is positive if $$$x > 0$$$. $$$^{\\text{‡}}$$$A sequence $$$a$$$ is lexicographically smaller than a sequence $$$b$$$ if and only if one of the following holds: - $$$a$$$ is a prefix of $$$b$$$, but $$$a \\ne b$$$; or - in the first position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

The first line contains an integer $$$t$$$ ($$$1 \\leq t \\leq 500$$$) — the number of test cases. The single line of each test case contains one integer $$$n$$$ ($$$2 \\le n \\le 2 \\cdot 10^5$$$) — the length of your array. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \\cdot 10^5$$$.

For each test case, output $$$n$$$ integers $$$a\_1, a\_2, \\dots, a\_n$$$ ($$$-10^9 \\leq a\_i \\leq 10^9$$$), the elements of your array on a new line.

In the first test case, because $$$a\_1 \\cdot a\_2 = -2 < 0$$$ and $$$a\_1 + a\_2 = 1 > 0$$$, it satisfies the two constraints. In addition, it can be shown that the corresponding $$$b = \[1, 2\]$$$ is better than any other good array of length $$$2$$$.