An có một bộ sưu tập gồm \(N\) đoạn thẳng nằm trên trục tọa độ \(Ox\). Đoạn thẳng thứ \(i\) được xác định bởi điểm bắt đầu \(L_i\) và điểm kết thúc \(R_i\).

Một đoạn thẳng \([L_i, R_i]\) được gọi là bao đoạn thẳng \([L_j, R_j]\) nếu \(L_i \le L_j\) và \(R_j \le R_i\). Với mỗi đoạn thẳng trong bộ sưu tập, An muốn đếm xem có bao nhiêu đoạn thẳng khác được bao bởi nó.

Hãy lập trình giúp An giải quyết bài toán đếm đoạn này.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(L_i, R_i\) mô tả đoạn thẳng thứ \(i\) (\(-10^9 \le L_i \le R_i \le 10^9\)).

Định dạng đầu ra

• In ra \(N\) số nguyên trên một dòng cách nhau bởi dấu cách, số thứ \(i\) là số lượng đoạn thẳng khác được bao bởi đoạn thẳng thứ \(i\).

Ví dụ

Input:

4
1 6
2 4
3 6
2 5

Output:

3 0 0 1