P16121 [USTCPC 2026] Is it paired?

克露丝卡尔酱邀请你来构造！ 克露丝卡尔酱有一个长度为 $n$ 的整数数组 $a$ 。克露丝卡尔酱在想，要是能让 $a$ 的所有子数组两两配对，配对的两个子数组的和相等，那该多好啊！ 克露丝卡尔酱想到了全0数组。这好像有点太简单了！于是她不允许数组中出现0了。现在你能帮她构造出满足要求的数组吗？

给定 $n$ , 构造一个长度为 $n$ 的整数数组 $a$，满足： - 对 $\forall i \in [1, n]$，有 $a_i \in [-10^9, 10^9] $ 且 $ a_i \neq 0 $。 - 取数组 $a$ 的**所有子数组的和** 放入 **可重集** $S$ , $S$中**每个元素**的出现次数均为 **偶数** 。 若不存在构造方案，输出一个 $0$ 并换行表示无解。**若有多个构造方案，输出任意一个即可**。 **注**：子数组是指在一个数组中，选择一些**连续**的元素组成的新数组。子数组**最少包含一个元素**。

**本题有多组测试数据** 第一行，输入一个正整数 $T$ $(1 \leq T \leq 40)$，表示数据组数。 接下来 $T$ 行，每行输入一个整数 $n$ $(1 \leq n \leq 1000)$, 表示需要构造的数组长度。

输出一共 $T$ 行，每一行表示一个 $n$ 的答案。 若不存在构造方案，输出一个整数 $0$ 并换行。 否则，在一行内输出 $n$ 个空格分隔的整数并换行，表示你的构造方案。 **注意你输出的构造方案需要满足 $a[i]\neq 0$**。

假设构造的数组是 {1,2,2,3} ，则先计算所有子数组的和： - 长度为 1 的子数组：1, 2, 2, 3 - 长度为 2 的子数组：3, 4, 5 - 长度为 3 的子数组：5, 7 - 长度为 4 的子数组：8 将这些子数组的和放入可重集 $S$ 中，得到 $S = \{1, 2, 2, 3, 3, 4, 5, 5, 7, 8\}$。其中元素 1 出现了 1 次，元素 2 出现了 2 次，元素 3 出现了 2 次，元素 4 出现了 1 次，元素 5 出现了 2 次，元素 7 出现了 1 次，元素 8 出现了 1 次。由于元素 1、4、7、8 的出现次数为奇数，因此这个数组不满足题目的要求。