Cho \(n\) đoạn, nhiệm vụ của bạn là đếm xem với mỗi đoạn chứa bao nhiêu đoạn khác và có bao nhiêu đoạn khác chứa nó.

Đoạn \([a, b]\) chứa đoạn \([c, d]\) nếu \(a \leq c\) và \(d \leq b\).

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\) \((1 \leq n \leq 2 \cdot 10^5)\) - số lượng đoạn
• Sau này, có \(n\) dòng mô tả các đoạn. Mỗi dòng có hai số nguyên \(x\) và \(y\) \((1 \leq x < y \leq 10^9)\) - đoạn là \([x,y]\)
• Bạn có thể giả định rằng không có đoạn nào xuất hiện nhiều hơn một lần trong đầu vào

Output

• Trước tiên, in một dòng mô tả cho mỗi đoạn (theo thứ tự đầu vào) có bao nhiêu đoạn khác mà nó chứa
• Sau đó, in một dòng mô tả cho mỗi đoạn (theo thứ tự đầu vào) có bao nhiêu đoạn khác chứa nó

Example

4
1 6
2 4
4 8
3 6

2 0 0 0
0 1 0 1