Bài toán: Đếm bao phủ giữa các đoạn

Đề bài

Cho ~ n ~ đoạn, nhiệm vụ của bạn là:

1. Đếm số lượng đoạn mà mỗi đoạn bao phủ.
2. Đếm số lượng đoạn bao phủ mỗi đoạn.

Một đoạn ~[a, b]~ bao phủ đoạn ~[c, d]~ nếu ~ a \leq c ~ và ~ d \leq b ~.

Input

• Dòng đầu tiên chứa số nguyên ~ n ~: số lượng đoạn.
• ~ n ~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~ x ~ và ~ y ~: đoạn ~[x, y]~.

Output

• Dòng đầu tiên chứa ~ n ~ số nguyên. Số thứ ~ i ~ là số đoạn mà đoạn ~ i ~ bao phủ.
• Dòng thứ hai chứa ~ n ~ số nguyên. Số thứ ~ i ~ là số đoạn bao phủ đoạn ~ i ~.

Ràng buộc

• ~ 1 \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq x < y \leq 10^9 ~

Ví dụ

Input:

4
1 6
2 4
4 8
3 6

Output:

2 0 0 0
0 1 0 1

Giải thích:

1. Dòng đầu tiên (số đoạn mà mỗi đoạn bao phủ):

   • ~ [1, 6] ~: bao phủ ~ [2, 4] ~ và ~ [3, 6] ~, nên giá trị là 2.
   • ~ [2, 4] ~: không bao phủ đoạn nào, giá trị là 0.
   • ~ [4, 8] ~: không bao phủ đoạn nào, giá trị là 0.
   • ~ [3, 6] ~: không bao phủ đoạn nào, giá trị là 0.

2. Dòng thứ hai (số đoạn bao phủ mỗi đoạn):

   • ~ [1, 6] ~: không bị đoạn nào bao phủ, giá trị là 0.
   • ~ [2, 4] ~: bị ~ [1, 6] ~ bao phủ, giá trị là 1.
   • ~ [4, 8] ~: không bị đoạn nào bao phủ, giá trị là 0.
   • ~ [3, 6] ~: bị ~ [1, 6] ~ bao phủ, giá trị là 1.