题目描述

平面上，给出 $n$ 条水平线段和 $n$ 条竖直线段，保证不同线段不在同一直线上。

若两线段有交点则它们连通，若 $a, b$ 连通且 $b, c$ 连通则 $a, c$ 连通。

一条线段 $a$ 是关键的，当且仅当存在另外两条线段 $b, c$，使得 $b, c$ 连通，且删去 $a$ 后 $b, c$ 不连通。

输入格式

第一行一个整数 $n$ 。

接下来 $n$ 行，第 $i$ 行有两个整数 $l, r$（$1 \le l < r \le n$），表示一条水平线段 $l \le x \le r$，$y=i$。

接下来 $n$ 行，第 $i$ 行有两个整数 $d, u$（$1 \le d < u \le n$），表示一条竖直线段 $x = i$，$d \le y \le u$。

输出格式

输出两行，每行是一个长度为 $n$ 的 $01$ 串。

第一行第 $i$ 位为 $1$ 当且仅当第 $i$ 条水平线段是关键的。

第二行第 $i$ 位为 $1$ 当且仅当第 $i$ 条竖直线段是关键的。

10
1 4
2 7
1 6
3 7
2 4
1 9
1 3
9 10
3 5
1 7
1 7
1 3
1 3
3 7
1 2
3 5
1 7
5 7
3 9
9 10

0100010000
1001000010

提示

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078&nzhtl1477

对于 $100\%$ 的数据，满足 $2 \le n \le 10^5$。