Kiểm tra Đoạn Lồng nhau

Cho $n$ đoạn thẳng, đoạn thứ $i$ có tọa độ $[x_i,y_i]$. Đoạn $[a,b]$ được gọi là chứa đoạn $[c,d]$ nếu $a\le c$ và $d\le b$.

Với mỗi đoạn thẳng, hãy xác định:

• Đoạn đó có chứa ít nhất một đoạn khác không?
• Đoạn đó có được chứa bởi ít nhất một đoạn khác không?

Dữ liệu vào

• Dòng đầu: số nguyên $n$ — số lượng đoạn thẳng.
• $n$ dòng tiếp theo, dòng thứ $i$: hai số nguyên $x_i$ và $y_i$ ($x_i<y_i$).

Dữ liệu ra

• Dòng 1: $n$ số nguyên $c_1,c_2,\dots ,c_n$, trong đó $c_i=1$ nếu đoạn $i$ chứa ít nhất một đoạn khác, ngược lại $c_i=0$.
• Dòng 2: $n$ số nguyên $d_1,d_2,\dots ,d_n$, trong đó $d_i=1$ nếu đoạn $i$ được chứa bởi ít nhất một đoạn khác, ngược lại $d_i=0$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le x_i<y_i\le {10}^9$
• Các đoạn đôi một phân biệt (không có hai đoạn hoàn toàn giống nhau).

Ví dụ