찬솔이는 $N$개의 노드에 정수가 적혀있는 이진 검색 트리를 만들었다. 이진 검색 트리는 모든 노드 $i$에 대해서, $i$의 왼쪽 자손 노드에 적힌 수는 모두 $i$에 적힌 수보다 작고, $i$의 오른쪽 자손 노드에 적힌 수는 모두 $i$에 적힌 수보다 큰 이진 트리이다.

찬솔이는 모든 $i$에 대해서 이진 검색 트리의 $i$번 노드의 깊이 $H_i$와 이진 검색 트리의 $i$번 노드에 적힌 정수 $A_i$를 기록해두었다. 이때, $A_i$는 모두 다르고 루트 노드의 깊이는 $1$이다. ($1 \le i \le N$)

찬솔이는 ICPC World Finals에 다녀오는 동안 이진 검색 트리를 잃어버렸다. 찬솔이를 위해 이전에 기록해둔 정보를 이용하여 이진 검색 트리를 복원해주자.

Input

첫 줄에 노드의 개수 $N$이 주어진다. ($1 \leq N \leq 200\,000$)

둘째 줄부터 $N$개의 줄에 걸쳐 트리의 노드 정보가 주어진다. 모든 $1 \leq i \leq N$에 대해, $(i+1)$번째 줄에는 $i$번 노드에 적힌 정수 $A_i$와 $i$번 노드의 깊이 $H_i$가 공백으로 구분되어 주어진다. ($-2\cdot 10^9\leq A_i \leq 2\cdot 10^9$; $1 \leq H_i \leq N$) $A_i$는 모두 다르다.

Output

만약 주어진 기록으로 이진 검색 트리를 복원할 수 없다면 $-1$을 출력한다.

복원할 수 있다면 트리의 구조를 $N$개의 줄에 걸쳐 출력한다.

$i$번째 줄에는 $i$번 노드의 왼쪽 자식과 오른쪽 자식의 노드 번호를 출력한다. 자식이 없으면 자식의 노드 번호로 $-1$을 출력한다.

만약 복원할 수 있는 트리가 여러 개라면 아무거나 복원해도 된다.

Examples

Input 1

3
1 2
2 1
3 2

Output 1

-1 -1
1 3
-1 -1

Input 2

3
1 1
2 2
3 2

Output 2

-1

Input 3

3
2 2
5 3
4 2

Output 3

-1

Input 4

3
100 2
200 1
300 2

Output 4

-1 -1
1 3
-1 -1