C. Racingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn 2077, a sport called hobby-droning is gaining popularity among robots.You already have a drone, and you want to win. For this, your drone needs to fly through a course with $$$n$$$ obstacles.The $$$i$$$-th obstacle is defined by two numbers $$$l_i, r_i$$$. Let the height of your drone at the $$$i$$$-th obstacle be $$$h_i$$$. Then the drone passes through this obstacle if $$$l_i \le h_i \le r_i$$$. Initially, the drone is on the ground, meaning $$$h_0 = 0$$$.The flight program for the drone is represented by an array $$$d_1, d_2, \ldots, d_n$$$, where $$$h_{i} - h_{i-1} = d_i$$$, and $$$0 \leq d_i \leq 1$$$. This means that your drone either does not change height between obstacles or rises by $$$1$$$. You already have a flight program, but some $$$d_i$$$ in it are unknown and marked as $$$-1$$$. Replace the unknown $$$d_i$$$ with numbers $$$0$$$ and $$$1$$$ to create a flight program that passes through the entire obstacle course, or report that it is impossible.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. In the first line of each test case, an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5)$$$ is given — the size of the array $$$d$$$.In the second line of each test case, there are $$$n$$$ integers $$$d_1, d_2, \ldots, d_n$$$ ($$$-1 \leq d_i \leq 1$$$) — the elements of the array $$$d$$$. $$$d_i = -1$$$ means that this $$$d_i$$$ is unknown to you.Next, there are $$$n$$$ lines containing $$$2$$$ integers $$$l_i,r_i$$$ ($$$0\leq l_i\leq r_i\leq n$$$) — descriptions of the obstacles.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$.OutputFor each test case, output $$$n$$$ integers $$$d_1,d_2,\ldots,d_n$$$, if it is possible to correctly restore the array $$$d$$$, or $$$-1$$$ if it is not possible.ExampleInput540 -1 -1 10 41 22 41 430 -1 -10 12 20 32-1 -10 02 28-1 -1 1 -1 -1 0 0 -10 00 10 20 21 30 42 54 5101 1Output0 1 1 1
-1
-1
0 1 1 0 1 0 0 1
-1
NoteIn the first test case, one possible answer is $$$d=[0,1,1,1]$$$. The array $$$h$$$ will be $$$[0,0+1,0+1+1,0+1+1+1]=[0,1,2,3]$$$. This array meets the conditions of the problem.In the second test case, it can be proven that there is no suitable array $$$d$$$, so the answer is $$$-1$$$.