Có ~n~ tảng đá đánh số từ 1 tới ~n~, một con ếch đang đứng ở tảng đá số 1 và muốn nhảy tới các tảng đá khác để kiếm mồi. Mỗi tảng đá ~i~ được gán một khoảng số nguyên ~[L_i, R_i]~ cho biết rằng nếu con ếch đứng ở tảng đá ~i~ thì bước nhảy tiếp theo nó phải nhảy tới một tảng đá thuộc phạm vi từ ~L_i~ tới ~R_i~.

Yêu cầu: Với mỗi tảng đá, cho biết số bước nhảy ít nhất con ếch cần thực hiện để đi tới tảng đá đó.

Input

• Dòng 1 chứa số nguyên dương ~n \le 2 \times 10^5~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~L_i, R_i~ (~\forall i: 1 \le L_i \le R_i \le n~).

Output

• Ghi ra gồm ~n~ số nguyên trên một dòng: số thứ ~i~ là số bước nhảy ít nhất của con ếch để đến tảng đá thứ ~i~, trong trường hợp con ếch không thể nhảy tới tảng đá thứ ~i~, số phải ghi là -1.

Sample Input 1

9
3 4
7 9
6 8
6 7
1 9
1 2
3 3
3 4
1 4

Sample Output 1

0 3 1 1 -1 2 2 2 4