Một chương trình gồm ~n~ lệnh được dùng để dựng nên một dãy gồm ~n~ số nguyên dương. Các lệnh được đánh số từ ~1~ đến ~n~ và chạy lần lượt theo thứ tự đó. Các phần tử của mọi dãy số đều được đánh số liên tiếp bắt đầu từ ~1~.

Mỗi lệnh có hai tham số ~x~ và ~y~, với ý nghĩa: chèn giá trị ~y~ vào dãy hiện tại sao cho ~y~ nằm ngay trước phần tử đang ở vị trí ~x~ (sau khi chèn, ~y~ chiếm vị trí ~x~).

• Lệnh đầu tiên dùng để tạo dãy một phần tử có giá trị ~s~, nên có tham số ~x = 1~ và ~y = s~.
• Muốn thêm giá trị ~t~ vào cuối một dãy đang có ~k~ phần tử, ta dùng lệnh với ~x = k + 1~ và ~y = t~.

Ví dụ: dãy hiện tại là 8 2 0 1 3, thực hiện lệnh với ~x = 2~, ~y = 6~ thì được dãy 8 6 2 0 1 3.

Hãy cho biết dãy số thu được sau khi chạy hết chương trình.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^3~) là số lệnh của chương trình.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~x~ và ~y~ (~1 \le x \le i + 1~, ~1 \le y \le 10^9~) là các tham số của lệnh thứ ~i~.

Kết quả

In ra ~n~ số nguyên dương là dãy nhận được sau khi thực hiện xong chương trình.

Ví dụ

SEQUENCE.INP

6
1 2
1 8
3 3
3 0
4 1
2 6

SEQUENCE.OUT

8 6 2 0 1 3