Cho \(n\) đoạn, nhiệm vụ của bạn là xác định xem với mỗi đoạn có chứa một số đoạn nào khác và có một số đoạn nào khác chứa nó hay không.

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

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): 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\): đ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) nếu nó chứa một số đoạn khác (1) hoặc không (0).
• Sau đó, in một dòng mô tả cho mỗi đoạn (theo thứ tự đầu vào) nếu có một số đoạn khác chứa nó (1) hoặc không (0).

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le x < y \le 10^9\)

Example

Sample input

4
1 6
2 4
4 8
3 6

1 0 0 0
0 1 0 1