C. 101
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Оценка массива $$$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$$$ была максимальной среди всех возможных способов замены $$$-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$$$ целых чисел, разделённых пробелами, представляющих массив $$$a$$$ после замены $$$-1$$$ на $$$0$$$ или $$$1$$$. Если существует несколько возможных решений, выведите любое.

Пример
Входные данные
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]$$$, то есть наибольший подмассив, удовлетворяющий условиям из условия, — это весь массив.