Cho \(n\) phạm vi, nhiệm vụ của bạn là xác định cho từng phạm vi xem nó có chứa một số phạm vi khác hay không và liệu một số phạm vi khác có chứa nó hay không.

Khoảng \([a, b]\) được cho là chứa khoảng \([c, d]\) nếu \(a \le c\) và \(d \le b\).

Đầu vào

Dòng đầu tiên chứa số nguyên \(n\), số phạm vi.

Tiếp theo, có \(n\) dòng mô tả các phạm vi. Mỗi dòng ghi hai số nguyên \(x\) và \(y\) cho phạm vi \([x,y]\).

Bạn có thể cho rằng không có phạm vi nào xuất hiện nhiều lần trong đầu vào.

Đầu ra

Đầu tiên, in một dòng mô tả cho từng phạm vi (theo thứ tự đầu vào) nếu nó chứa một số phạm vi khác (1) hoặc không (0).

Sau đó, in một dòng mô tả cho từng phạm vi (theo thứ tự đầu vào) nếu một số phạm vi khác chứa nó (1) hoặc không (0).

Giới hạn

\(1 \le n \le 2*10^5\)

\(1 \le x < y \le 10^9\)

Ví dụ

Đầu vào:

4
1 6
2 4
4 8
3 6

Đầu ra:

1 0 0 0
0 1 0 1