Đếm Đoạn Bao Chứa · canuc80k3914

Cho $n$ đoạn đóng đôi một khác nhau. Với mỗi đoạn, hãy đếm số đoạn khác nằm hoàn toàn trong nó và số đoạn khác chứa hoàn toàn nó.

Input

Dòng đầu chứa số nguyên $n$ .
Mỗi trong $n$ dòng tiếp theo chứa hai số nguyên $x_{i}$ và $y_{i}$ , biểu diễn đoạn $[x_{i}, y_{i}]$ .

Output

Dòng đầu in $n$ số; số thứ $i$ là số đoạn khác nằm trong đoạn $i$ .
Dòng thứ hai in $n$ số; số thứ $i$ là số đoạn khác chứa đoạn $i$ .

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq x_{i} < y_{i} \leq 1 0^{9}$ .
Không có hai đoạn hoàn toàn giống nhau.
Đoạn $[a, b]$ chứa $[c, d]$ khi $a \leq c$ và $d \leq b$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 12$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

4 1 0 0 2
0 2 3 1 1

Giải thích: Đoạn $[1, 10]$ chứa cả bốn đoạn còn lại; $[1, 7]$ chứa $[2, 5]$ và $[3, 4]$ . Chẳng hạn $[3, 4]$ được ba đoạn $[1, 10], [2, 5], [1, 7]$ chứa.

Ý tưởng: Sắp theo đầu trái tăng, đầu phải giảm; dùng hai lượt Fenwick trên đầu phải đã nén để đếm hai chiều chứa.
Ý tưởng: 1. Nén tất cả đầu phải và sắp đoạn theo (x tăng,y giảm). 2. Quét từ phải sang trái: số đầu phải đã chèn không vượt y_i là số đoạn nằm trong i. 3. Quét từ trái sang phải: số đầu phải đã chèn không nhỏ hơn y_i là số đoạn chứa i. 4. Ghi kết quả theo chỉ số ban đầu.
Tính đúng đắn: 1. Ở lượt phải sang trái, mọi đoạn đã chèn có đầu trái không nhỏ hơn x_i; thêm điều kiện đầu phải≤y_i đúng chính xác quan hệ nằm trong. 2. Ở lượt trái sang phải, mọi đoạn đã chèn có đầu trái không lớn hơn x_i; thêm điều kiện đầu phải≥y_i đúng chính xác quan hệ chứa. 3. Thứ tự y giảm khi x bằng nhau bảo đảm các đoạn có cùng đầu trái xuất hiện đúng phía trong hai lượt.
Độ phức tạp: O(n log n) thời gian và O(n) bộ nhớ.
Lưu ý cài đặt: Khi x bằng nhau phải sắp y giảm.
Lưu ý cài đặt: Kết quả phải trả theo thứ tự input.