You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp has invited $$$n$$$ friends to celebrate the New Year. During the celebration, he decided to take a group photo of all his friends. Each friend can stand or lie on the side.

Each friend is characterized by two values $$$h_i$$$ (their height) and $$$w_i$$$ (their width). On the photo the $$$i$$$-th friend will occupy a rectangle $$$h_i \times w_i$$$ (if they are standing) or $$$w_i \times h_i$$$ (if they are lying on the side).

The $$$j$$$-th friend can be placed in front of the $$$i$$$-th friend on the photo if his rectangle is lower and narrower than the rectangle of the $$$i$$$-th friend. Formally, at least one of the following conditions must be fulfilled:

- $$$h_j < h_i$$$ and $$$w_j < w_i$$$ (both friends are standing or both are lying);
- $$$w_j < h_i$$$ and $$$h_j < w_i$$$ (one of the friends is standing and the other is lying).

For example, if $$$n = 3$$$, $$$h=[3,5,3]$$$ and $$$w=[4,4,3]$$$, then:

- the first friend can be placed in front of the second: $$$w_1 < h_2$$$ and $$$h_1 < w_2$$$ (one of the them is standing and the other one is lying);
- the third friend can be placed in front of the second: $$$h_3 < h_2$$$ and $$$w_3 < w_2$$$ (both friends are standing or both are lying).

In other cases, the person in the foreground will overlap the person in the background.

Help Polycarp for each $$$i$$$ find any $$$j$$$, such that the $$$j$$$-th friend can be located in front of the $$$i$$$-th friend (i.e. at least one of the conditions above is fulfilled).

Please note that you do not need to find the arrangement of all people for a group photo. You just need to find for each friend $$$i$$$ any other friend $$$j$$$ who can be located in front of him. Think about it as you need to solve $$$n$$$ separate independent subproblems.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of friends.

This is followed by $$$n$$$ lines, each of which contains a description of the corresponding friend. Each friend is described by two integers $$$h_i$$$ and $$$w_i$$$ ($$$1 \leq h_i, w_i \leq 10^9$$$) — height and width of the $$$i$$$-th friend, respectively.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case output $$$n$$$ integers on a separate line, where the $$$i$$$-th number is the index of a friend that can be placed in front of the $$$i$$$-th. If there is no such friend, then output -1.

If there are several answers, output any.

## Examples
```input
4
3
3 4
5 4
3 3
3
1 3
2 2
3 1
4
2 2
3 1
6 3
5 4
4
2 2
2 3
1 1
4 4
```
```output
-1 3 -1 
-1 -1 -1 
-1 -1 2 2 
3 3 -1 3
```

## Note
The first test case is described in the statement.

In the third test case, the following answers are also correct:

- $$$[-1, -1, 1, 2]$$$;
- $$$[-1, -1, 1, 1]$$$;
- $$$[-1, -1, 2, 1]$$$.

Now solve the problem and return the code.