题目背景

翻译自 CSES-2168 题。

题目描述

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

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

输入格式

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

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

保证每个区间在输入中至多出现一次。

输出格式

第一行输出 $n$ 个整数，第 $i$ 个整数描述第 $i$ 个区间是否包含其他区间（1 表示包含，0 表示不包含），按输入顺序输出。

第二行输出 $n$ 个整数，第 $i$ 个整数描述第 $i$ 个区间是否被其他区间包含（1 表示被包含，0 表示不被包含），按输入顺序输出。

样例

4
1 6
2 4
4 8
3 6

1 0 0 0
0 1 0 1

样例解释

• 区间 $[1,6]$ 包含 $[2,4]$ 和 $[3,6]$，所以第一行第 1 个数为 1；
• 区间 $[2,4]$ 被 $[1,6]$ 包含，$[3,6]$ 被 $[1,6]$ 包含，所以第二行第 2、4 个数为 1；
• 区间 $[4,8]$ 既不包含别人，也不被别人包含。

数据范围

• 对于 $30\%$ 的测试点，保证 $1 \le n \le 1000$；
• 对于 $100\%$ 的测试点，保证 $1 \le n \le 2 \times 10^5$，$1 \le x < y \le 10^9$。