题目背景

And it’s not the voice of all the others

You’ve only said it to yourself

I know what you want from me, from me

I know what you’re thinking

题目描述

Porter Robinson: We all have these avatars that we give to our critical inner voices - we might imagine a scornful parent telling us we’ll fail, or a critic telling us our work comes up short, or a society telling us that we aren’t good enough - it’s about recognizing that most of this criticism is self-inflicted.

Mivik 在镜中看见了自己的 Inner Voice ——不过是在一个镜子般对称的迷宫中。这个迷宫很特殊：它有无穷多行和无穷多列，行和列都从 $0$ 开始标号。一个格子 $(i,j)$ 能通过（没有障碍）当且仅当 $(i\&j)=0$，其中 $\&$ 指按位与运算（Bitwise And，百度百科）。下图给出了这个迷宫的 $0\sim63$ 行和 $0\sim 63$ 列的图像：

Mivik 想抓到并消灭那个给予自己负面声音的 Inner Voice，但他找不到路了。Mivik 和 Inner Voice 最初处在迷宫中的两点。Mivik 想知道，在 Mivik 的 Inner Voice 一直不移动的情况下，他至少需要走过多少个方格才能抓到他的 Inner Voice（Mivik 的起始格不算）。

但是... 游戏并不会像 Mivik 想象的一样简单。邪恶的 ggy 在这个迷宫中的某些格子布下了许多炸弹，Mivik 需要拆除它们才能踏上这些格子。Mivik 需要你告诉他，在他走过的方格数最少的情况下，他至少需要拆除哪些炸弹。

请注意炸弹可能会重合，而你只有拆除一个格子上的所有炸弹才能通过这个格子。保障炸弹不与起点重合。

输入格式

第一行一个整数 $n$，代表 ggy 设下的炸弹个数。

接下来 $n$ 行，其中的第 $i$ 行两个非负整数，代表 $i$ 号炸弹的坐标（从 1 开始编号）。

接下来一行两个非负整数 $sx$ 和 $sy$，代表 Mivik 位于哪一行哪一列。

接下来一行两个非负整数 $ex$ 和 $ey$，代表 Mivik 的 Inner Voice 位于哪一行哪一列。

输出格式

第一行一个整数，代表 Mivik 至少需要走少格才能抓到他的 Inner Voice。

接下来一行，给出一个长度为 $n$ 的 01 串，第 $i$ 个字符为 1 代表 Mivik 必须拆除第 $i$ 号炸弹，0 代表不需要。

0
0 0
0 2

2

3
0 0
0 2
1 2
4 2
3 4

13
110

0
12 34
3 100

85

提示

样例解释

样例一：显然由于没有任何炸弹，Mivik 向右走两格就能抓到他的 Inner Voice。

样例二：Mivik 的最短路径如图所示：

其中，图片左上角为 $(0,0)$，蓝色代表 Mivik 的起始位置，绿色代表 Inner Voice 的位置，红色代表 Mivik 的最短路径，黄色代表炸弹，橙色（其实是黄色 + 红色）代表 Mivik 必须拆除的炸弹。

数据范围

对于全部数据，有 $1\le n\le 2\cdot 10^5$，$(sx,sy)\ne(ex,ey)$，并保证对于给出的任何坐标 $(x,y)$ 都有 $x\&y=0$ 且 $0\le x,y\le 10^{18}$。

Subtask 1 (10 pts)：保证 Mivik 可以直线（只向 上/下/左/右 走）抓到他的 Inner Voice。

Subtask 2 (15 pts)：保证 $sx=sy=0$。

Subtask 3 (20 pts)：保证 $0\le(\text{任意 x,y 坐标})\le 100$。

Subtask 4 (25 pts)：保证 $n=0$。

Subtask 5 (30 pts)：无特殊限制。