Chansol đã tạo một cây tìm kiếm nhị phân gồm $N$ nút, mỗi nút được ghi một số nguyên. Cây tìm kiếm nhị phân là một cây nhị phân sao cho với mọi nút $i$, tất cả các số ghi trên các nút thuộc cây con trái của $i$ đều nhỏ hơn số ghi trên $i$, và tất cả các số ghi trên các nút thuộc cây con phải của $i$ đều lớn hơn số ghi trên $i$.

Chansol đã ghi lại độ sâu $H_i$ của nút $i$ và số nguyên $A_i$ ghi trên nút $i$ của cây tìm kiếm nhị phân, với mọi $i$. Ở đây, các giá trị $A_i$ đôi một khác nhau và độ sâu của nút gốc là $1$. ($1 \le i \le N$)

Trong thời gian Chansol đi tham dự ICPC World Finals, cây tìm kiếm nhị phân đã bị thất lạc. Hãy giúp Chansol khôi phục lại cây tìm kiếm nhị phân từ các thông tin đã ghi lại.

Dữ liệu vào

Dòng đầu tiên chứa số lượng nút $N$. ($1 \leq N \leq 200\,000$)

$N$ dòng tiếp theo, mỗi dòng chứa thông tin về một nút của cây. Với mọi $1 \leq i \leq N$, dòng thứ $(i+1)$ chứa số nguyên $A_i$ ghi trên nút $i$ và độ sâu $H_i$ của nút $i$, cách nhau bởi một dấu cách. ($-2\cdot 10^9\leq A_i \leq 2\cdot 10^9$; $1 \leq H_i \leq N$) Các giá trị $A_i$ đôi một khác nhau.

Dữ liệu ra

Nếu không thể khôi phục cây tìm kiếm nhị phân từ các thông tin đã cho, in ra $-1$.

Nếu có thể khôi phục, in ra cấu trúc của cây trên $N$ dòng.

Dòng thứ $i$ in ra số hiệu của nút con trái và nút con phải của nút $i$. Nếu không có con, in ra $-1$ thay cho số hiệu nút con.

Nếu có nhiều cây có thể khôi phục, bạn có thể in ra bất kỳ cây nào.

Ví dụ

Dữ liệu vào 1

3
1 2
2 1
3 2

Dữ liệu ra 1

-1 -1
1 3
-1 -1

Dữ liệu vào 2

3
1 1
2 2
3 2

Dữ liệu ra 2

-1

Dữ liệu vào 3

3
2 2
5 3
4 2

Dữ liệu ra 3

-1

Dữ liệu vào 4

3
100 2
200 1
300 2

Dữ liệu ra 4

-1 -1
1 3
-1 -1