In 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.

Input

Each 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$.

Output

For 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.

Note

In 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$.