P16121 [USTCPC 2026] Is it paired?

Kruskal-chan invites you to construct one! Kruskal-chan has an integer array $a$ of length $n$. She is thinking: how nice it would be if all subarrays of $a$ could be paired up, and the two subarrays in each pair have equal sums! Kruskal-chan thought of the all-zero array. That seems a bit too easy! So she does not allow zeros in the array anymore. Can you help her construct an array that satisfies the requirements?

Given $n$, construct an integer array $a$ of length $n$ such that: - For $\forall i \in [1, n]$, $a_i \in [-10^9, 10^9]$ and $a_i \neq 0$. - Put the **sums of all subarrays** of array $a$ into a **multiset** $S$. The number of occurrences of **every element** in $S$ must be **even**. If no construction exists, output $0$ followed by a newline to indicate there is no solution. **If there are multiple constructions, output any one of them**. **Note**: A subarray means selecting some **consecutive** elements in an array to form a new array. A subarray contains **at least one element**.

**This problem has multiple test cases.** The first line contains a positive integer $T$ $(1 \leq T \leq 40)$, the number of test cases. The next $T$ lines each contain an integer $n$ $(1 \leq n \leq 1000)$, the length of the array to construct.

Output a total of $T$ lines, each line giving an answer for one $n$. If no construction exists, output an integer $0$ and a newline. Otherwise, output $n$ integers separated by spaces on one line and end with a newline, representing your construction. **Note that your construction must satisfy $a[i] \neq 0$.**

Suppose the constructed array is {1,2,2,3}. First compute the sums of all subarrays: - Subarrays of length 1: 1, 2, 2, 3 - Subarrays of length 2: 3, 4, 5 - Subarrays of length 3: 5, 7 - Subarrays of length 4: 8 Put these subarray sums into multiset $S$,得到 $S = \{1, 2, 2, 3, 3, 4, 5, 5, 7, 8\}$. Element 1 appears 1 time, element 2 appears 2 times, element 3 appears 2 times, element 4 appears 1 time, element 5 appears 2 times, element 7 appears 1 time, and element 8 appears 1 time. Since the occurrence counts of elements 1, 4, 7, and 8 are odd, this array does not satisfy the requirements. Translated by ChatGPT 5