问题描述

长度为 ~m~ 的数组 ~b~ 的分数定义为 ~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~ 的分数最大。

输入

每个输入的第一行包含 ~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~。

输出

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

样例输入

10
6
1 0 -1 0 0 1
7
0 -1 0 0 1 0 1
5
-1 0 0 -1 0
4
0 0 0 0
1
-1
6
1 0 1 0 0 -1
7
0 1 0 0 0 1 0
6
-1 -1 -1 -1 -1 -1
7
-1 0 1 -1 0 0 1
3
-1 0 0

样例输出

1 0 0 0 0 1
0 1 0 0 1 0 1
1 0 0 1 0
0 0 0 0
1
1 0 1 0 0 1
0 1 0 0 0 1 0
1 0 0 0 0 1
0 0 1 0 0 0 1
1 0 0

说明

在第一组测试用例中，我们可以把唯一的 ~-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]~，这意味着满足题面条件的最长子数组是整个数组。