题目描述

有 $n$ 个人分仓鼠吃，每个人分到的仓鼠有两个属性：大小 $s$、美味值 $t$。

第 $i$ 个人心中有两个值 $l_i,r_i$。若其后连续一段人 $[i+1,j]$ 的平均美味值不在区间 $[l_i,r_i]$ 内，他就会看第 $j$ 个人不顺眼。

现在你知道了所有这些信息，并想知道哪些人会看别人不顺眼，以及哪些人会被别人看不顺眼。

由于答案可能很大，你只需要分别输出：

• 哪些人会看别人不顺眼；
• 哪些人会被别人看不顺眼。

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含四个整数 $s_i,t_i,l_i,r_i$。

输出格式

输出两行 01 串，每行长度均为 $n$。

• 第一行的第 $i$ 个字符表示第 $i$ 个人是否会看别人不顺眼；
• 第二行的第 $i$ 个字符表示第 $i$ 个人是否会被别人看不顺眼。

其中，字符 1 表示“是”，字符 0 表示“否”。

样例 1

输入

3
4 24 5 7
16 128 4 12
16 64 0 8

输出

100
010

样例 2

输入

5
2 15 7 8
16 128 4 12
16 64 0 8
20 160 3 13
20 160 3 13

输出

10000
00110

数据范围

对于 $100\%$ 的数据：

$$n\le 100000, \qquad t_i\le 10^8, \qquad s_i,l_i,r_i\le 10^4.$$

测试点编号	分数	$n$
1	10	$20$
2		$100$
3	20	$1000$
4	60	$100000$