J. Billboard
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Xiaomei is watching a video about the popular song rankings from recent years. When she sees various comments on the screen like "too high", "too low", and "reasonable", her train of thought is disrupted. However, she also believes that the current ranking list is not very reasonable. Therefore, she wants to create a new list based on these comments.

Since there are too many comments, Xiaomei will collect and consolidate a more unified opinion for each song. There are three types of opinions:

  • $$$\texttt{1 x}$$$: The song ranked $$$x$$$ is too high, and it should be lower.
  • $$$\texttt{-1 x}$$$: The song ranked $$$x$$$ is too low, and it should be higher.
  • $$$\texttt{0 x}$$$: The song ranked $$$x$$$ is reasonably ranked, and it should not be changed.

Each song has exactly one consolidated opinion. Xiaomei wants to know if it is possible to create a new list that satisfies all the opinions.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 300$$$), representing the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), representing the number of songs on the list.

Each of the next $$$n$$$ lines contains two integers $$$p$$$ and $$$x$$$ ($$$-1 \le p \le 1$$$, $$$1 \le x \le n$$$), representing an opinion for the song ranked $$$x$$$. It is guaranteed that each song has exactly one opinion.

It is guaranteed that $$$\sum n \le 2 \times 10^5$$$ over all test cases.

Output

For each test case, output $$$n$$$ integers in a single line representing the new list of the song board if a satisfactory list can be created, where the $$$i$$$-th integer $$$a_i$$$ indicates that the new rank of the song originally ranked $$$a_i$$$ is $$$i$$$. If there are multiple solutions, output any. If there is no solution, output $$$\texttt{-1}$$$ in a single line.

Example
Input
2
2
1 1
-1 2
5
0 2
-1 3
-1 4
0 1
-1 5
Output
2 1
-1