Description

在平面直角坐标系上给定 $n$ 个矩形，形成若干个交点，每个矩形的所有边都平行于坐标轴。保证没有两个矩形的两条边共线。

矩形之间会形成若干个交点，每一个矩形都被它上面的交点分成若干段。定义属于一个矩形上的一段是该矩形上相邻的两个交点之间的部分。也就是说一个矩形上如果有 $n$ 个交点，就会被划分成 $n$ 段。

现在将每一个矩形上的每一段染色为蓝色或红色。要求：

• 与同一个交点相邻的同属于一个矩形的两段不同色；
• 所有红线形成若干互不相交的封闭曲线；
• 所有蓝线形成若干互不相交的封闭曲线。

定义两个图形 $R,B$：

• $R$ 为删去所有蓝线后，所有被奇数个红色封闭曲线包含的点组成的集合；
• $B$ 为删去所有红线后，所有被奇数个蓝色封闭曲线包含的点组成的集合。

一个方案合法当且仅当它满足上述所有条件，并且使得 $R\cap B$ 里面只有有限个点。

如果无法理解上述定义，可以参考样例解释。

你需要分别求出：

• 字典序最小的合法染色方案（字典序在输出格式里面有定义）。
• 合法染色方案数，对 $20,051,131$（质数）取模。两个染色方案不同当且仅当存在一段，在一种方案中被染成红色，在另一种方案中被染成蓝色。

Input Format

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行 4 个整数 $x_{1,i},y_{1,i},x_{2,i},y_{2,i}$，前两个表示左下角坐标，后两个表示右上角坐标。

Output Format

第一行输出字典序最小的合法方案：如果无解，输出一行 -1；否则输出一个长度为 $n$ 的 0/1 串。如果在你的方案中，按输入顺序给出的第 $i$ 个矩形的左下角是红色，则你输出的第 $i$ 个整数应该是 $0$；否则应该是 $1$。可以证明给定这些数之后能够唯一确定整个染色方案。如果有多解，你输出的解必须使得上面描述的 01 序列字典序最小。

第二行输出合法染色方案数，对 $20,051,131$ 取模。无解时应输出 $0$。

2
1 2 3 3
2 1 4 4

01
2

4
1 1 5 5
2 2 6 6
3 3 7 7
4 4 8 8

0000
2

2
1 1 4 4
2 2 3 3

00
2

3
1 2 4 5
2 3 5 6
3 1 6 4

-1
0

Hint

样例 5、6、7 见附件。

---

样例 1 解释：

如图是给定的矩形在平面直角坐标系上的形态。

如图，标出颜色的地方是属于第 1 个矩形的两段。

如图，标出颜色的地方是属于第 2 个矩形的两段。按照上述图片给出的颜色进行染色可以得到样例输出中给出的合法方案：

如下图，左侧方案是不合法的，因为与用圈标出的交点相邻的同属于一个矩形的两段同色；右侧方案也是不合法的，因为 $R$ 与 $B$ 交在图中的紫色正方形内，$R\cap B$ 包含无限多个点。

如下方案是合法的，但是对应字符串 10 不是字典序最小的。

---

样例 2 解释：

左侧的图为给定的所有矩形。

中间的图表示对应的染色方案。每一个矩形都包含 $6$ 段，并且满足与任何一个交点相邻的同属于一个矩形的两段不同色。

右侧的图中，用红色区域标出 $R$ 的范围，蓝色区域标出 $B$ 的范围。两图形的交只包含 $12$ 个点。

---

样例 3 解释：

如图，该样例中，因为环内部的部分被 $2$ 条红色封闭曲线包含，$2$ 是偶数，所以环内部不属于 $R$，$R$ 形成一个环。

---

数据范围：

对于 $100\%$ 的数据，保证 $1\leq n\leq 2\times 10^5$，$x_{1,i}<x_{2,i}$，$y_{1,i}<y_{2,i}$，$\{x_{i,j}|1\leq i\leq 2,1\leq j\leq n\}=\{y_{i,j}|1\leq i\leq 2,1\leq j\leq n\}=\{1,2,3,\cdots,2n\}$。

• Subtask 1（5 pts）：矩形之间互不相交。
• Subtask 2（20 pts）：$n\leq 13$。
• Subtask 3（20 pts）：$n\leq 200$。
• Subtask 4（25 pts）：$n\leq 2000$。
• Subtask 5（30 pts）：无特殊限制。