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

В 2077 году среди роботов набирает популярность вид спорта под названием хобби-дроннинг.

У вас уже есть дрон, и вы хотите выиграть. Для этого вашему дрону нужно пролететь полосу с $$$n$$$ препятствиями.

$$$i$$$-е препятствие задается двумя числами $$$l_i, r_i$$$. Пусть высота вашего дрона на $$$i$$$-м препятствии равна $$$h_i$$$. Тогда дрон пролетает через это препятствие, если $$$l_i \le h_i \le r_i$$$. Изначально дрон стоит на земле, то-есть $$$h_0 = 0$$$.

Программа полета для дрона представляет из себя массив $$$d_1, d_2, \ldots, d_n$$$, где $$$h_{i} - h_{i-1} = d_i$$$, причем $$$0 \leq d_i \leq 1$$$. Это значит, что ваш дрон либо не меняет высоту между препятствиями, либо поднимается на $$$1$$$. У вас уже есть программа полета, однако некоторые $$$d_i$$$ в ней вам неизвестны и помечены как $$$-1$$$. Замените неизвестные $$$d_i$$$ на числа $$$0$$$ и $$$1$$$, чтобы получилась программа полета, которая пролетает всю полосу препятствий, или сообщите, что это невозможно.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных вводится целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5)$$$ — размер массива $$$d$$$.

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ ($$$-1 \leq d_i \leq 1$$$) — элементы массива $$$d$$$. $$$d_i = -1$$$ означает, что данное $$$d_i$$$ вам неизвестно.

Далее в $$$n$$$ строках содержится по $$$2$$$ целых числа $$$l_i,r_i$$$ ($$$0\leq l_i\leq r_i\leq n$$$) — описания препятствий.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$d_1,d_2,\ldots,d_n$$$, если возможно корректно восстановить массив $$$d$$$, или $$$-1$$$, если не возможно.

Пример
Входные данные
5
4
0 -1 -1 1
0 4
1 2
2 4
1 4
3
0 -1 -1
0 1
2 2
0 3
2
-1 -1
0 0
2 2
8
-1 -1 1 -1 -1 0 0 -1
0 0
0 1
0 2
0 2
1 3
0 4
2 5
4 5
1
0
1 1
Выходные данные
0 1 1 1 
-1
-1
0 1 1 0 1 0 0 1 
-1
Примечание

В первом наборе входных данных одним из возможных ответов это $$$d=[0,1,1,1]$$$. Массив $$$h$$$ будет равен $$$[0,0+1,0+1+1,0+1+1+1]=[0,1,2,3]$$$. Такой массив подходит под условия задачи.

Во втором наборе входных данных можно доказать, что не существует подходящего массива $$$d$$$, поэтому ответ $$$-1$$$.