CF2259C.101

The score of an array $b$ of length $m$ is defined as the maximum length of a subarray of $b$ such that the first and last elements of the subarray are equal to $1$ and all other elements in the subarray are equal to $0$. Formally, the score of $b$ is equal to the maximum integer $k$ for which there exists an index $i$ such that:

• $1 \leq i \leq m - k + 1$
• $b_i = b_{i+k-1} = 1$
• $b_{i+1} = b_{i+2} = \ldots = b_{i+k-2} = 0$

If there is no subarray meeting the requirements, the score of $b$ is $0$.

You are given an array $a_1, a_2, \ldots, a_n$, such that each element is equal to one of $-1$, $0$, or $1$. Replace each $-1$ with either a $0$ or $1$ such that the score of $a$ is maximal over all possible ways to replace the $-1$s in $a$.

数组 $b$（长度为 $m$）的得分定义为：$b$ 中满足“子数组首尾元素均为 $1$，且中间所有元素均为 $0$”的最长子数组的长度。形式化地，$b$ 的得分等于最大的整数 $k$，使得存在下标 $i$ 满足：

• $1 \leq i \leq m - k + 1$
• $b_i = b_{i+k-1} = 1$
• $b_{i+1} = b_{i+2} = \ldots = b_{i+k-2} = 0$

若不存在满足要求的子数组，则 $b$ 的得分为 $0$。

给定一个数组 $a_1, a_2, \ldots, a_n$，其中每个元素为 $-1$、$0$ 或 $1$ 之一。请将每个 $-1$ 替换为 $0$ 或 $1$，使得替换后数组 $a$ 的得分在所有可能的替换方式中达到最大。

The first line of each input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of $a$.

The second line of each test case contains $a_1, a_2, \ldots, a_n$ ($a_i \in {-1, 0, 1}$) — the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每组输入的第一行包含 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $a_1, a_2, \ldots, a_n$（其中 $a_i \in \{-1, 0, 1\}$）—— 数组 $a$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output $n$ space separated integers representing $a$ after the $-1$s were replaced with $0$s or $1$s. If there are multiple possible solutions, output any.

对于每个测试用例，输出 $n$ 个以空格分隔的整数，表示将 $a$ 中的所有 $-1$ 替换为 $0$ 或 $1$ 后的结果。如果存在多种可能的解，输出任意一个即可。

In the first test case, we can change the only $-1$ to a $0$, making $a = [1, 0, 0, 0, 0, 1]$. Since the first and last elements of $a$ are equal to $1$, and all other elements are $0$, the score of $a$ is $6$.

In the third test case, changing both $-1$s to $1$s makes $a = [1, 0, 0, 1, 0]$, and the largest subarray that satisfies the conditions in the statement is from the $1$-st index to the $4$-th index.

In the fifth test case, we set the only $-1$ to $1$, making $a = [1]$, meaning the largest subarray that satisfies the conditions in the statement is the full array.

在第一个测试用例中，我们可以将唯一的 $-1$ 改为 $0$，从而得到 $a = [1, 0, 0, 0, 0, 1]$。由于 $a$ 的首尾元素均为 $1$，且其余所有元素均为 $0$，因此 $a$ 的得分为 $6$。

在第三个测试用例中，将两个 $-1$ 均改为 $1$，可得 $a = [1, 0, 0, 1, 0]$，此时满足题目所述条件的最长子数组是从第 $1$ 个下标到第 $4$ 个下标。

在第五个测试用例中，我们将唯一的 $-1$ 设为 $1$，得到 $a = [1]$，这意味着满足题目所述条件的最长子数组即为整个数组。