Đề bài

Cho ~ n ~ đoạn, nhiệm vụ của bạn là kiểm tra cho mỗi đoạn xem:

1. Nó có bao phủ đoạn nào khác không?
2. Có đoạn nào khác bao phủ nó không?

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 một 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

• In hai dòng:
  • Dòng đầu tiên chứa ~ n ~ số nguyên (0 hoặc 1). Số thứ ~ i ~ là 1 nếu đoạn ~ i ~ bao phủ ít nhất một đoạn khác, ngược lại là 0.
  • Dòng thứ hai chứa ~ n ~ số nguyên (0 hoặc 1). Số thứ ~ i ~ là 1 nếu có ít nhất một đoạn bao phủ đoạn ~ i ~, ngược lại là 0.

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:

1 0 0 0
0 1 0 1

Giải thích:

• Dòng đầu tiên:

  • Đoạn ~ [1, 6] ~ bao phủ ~ [2, 4] ~, nên là 1.
  • Các đoạn còn lại không bao phủ đoạn nào, nên là 0.

• Dòng thứ hai:

  • Đoạn ~ [2, 4] ~ được bao phủ bởi ~ [1, 6] ~, nên là 1.
  • Đoạn ~ [4, 8] ~ không được bao phủ bởi đoạn nào, nên là 0.
  • Đoạn ~ [3, 6] ~ được bao phủ bởi ~ [1, 6] ~, nên là 1.