题目描述

给定 $n$ 个区间，你的任务是判断每个区间是否包含其他区间，或者是否被其他区间包含。

如果有 $a \le c$ 和 $d \le b$，那么区间 $[a, b]$ 包含区间 $[c, d]$。

输入格式

第一行输入一个整数 $n$，代表区间数。

之后有 $n$ 行描述区间。每行有两个整数 $x$ 和 $y$，分别代表区间为 $[x, y]$。

可以假设每个区间在输入中出现的次数不超过一次。

输出格式

首先输出一行，描述每个区间是否包含其他区间（$1$ 表示包含，$0$ 表示不包含）。按输入顺序输出。

然后输出一行，描述每个区间是否被其他区间包含（$1$ 表示被包含，$0$ 表示不被包含）。按输入顺序输出。

样例

4
1 6
2 4
4 8
3 6

1 0 0 0
0 1 0 1

数据范围

• $1 \le n \le 2 \times 10^5$
• $1 \le x < y \le 10^9$