P7264 Mirror

 > 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 sees his Inner Voice in the mirror, but it is inside a mirror-symmetric maze. This maze is special: it has infinitely many rows and infinitely many columns, and both rows and columns are numbered starting from $0$. A cell $(i,j)$ is passable (has no obstacle) if and only if $(i\&j)=0$, where $\&$ denotes the bitwise AND operation (Bitwise And, [Baidu Baike](https://baike.baidu.com/item/%E6%8C%89%E4%BD%8D%E4%B8%8E/9601818)). The image below shows rows $0\sim63$ and columns $0\sim63$ of this maze:  Mivik wants to catch and destroy the Inner Voice that gives him negative thoughts, but he cannot find the way. Mivik and Inner Voice initially stay at two points in the maze. Mivik wants to know, when Inner Voice never moves, what is the minimum number of cells he must walk through to catch Inner Voice (Mivik’s starting cell is not counted). However, the game will not be as simple as Mivik imagines. The evil ggy has placed many bombs on some cells in this maze, and Mivik must defuse them before stepping onto those cells. You need to tell Mivik, when the number of cells he walks through is minimized, which bombs he must defuse at minimum. **Note that bombs may overlap, and you can pass a cell only after defusing all bombs on that cell. It is guaranteed that no bomb overlaps with the starting position.**

The first line contains an integer $n$, representing the number of bombs placed by ggy. The next $n$ lines: the $i$-th line contains two non-negative integers, representing the coordinate of bomb $i$ (numbered starting from $1$). The next line contains two non-negative integers $sx$ and $sy$, representing which row and which column Mivik is in. The next line contains two non-negative integers $ex$ and $ey$, representing which row and which column Mivik’s Inner Voice is in.

The first line contains an integer, representing the minimum number of cells Mivik needs to walk through to catch his Inner Voice. The next line contains a 01 string of length $n$. The $i$-th character is `1` if Mivik must defuse bomb $i$, and `0` otherwise.

### Sample Explanation Sample 1: Obviously, since there are no bombs, Mivik can catch his Inner Voice by moving two cells to the right. Sample 2: Mivik’s shortest path is shown in the figure:  In the figure, the top-left corner is $(0,0)$. Blue indicates Mivik’s starting position, green indicates Inner Voice’s position, red indicates Mivik’s shortest path, yellow indicates bombs, and orange (actually yellow + red) indicates the bombs that Mivik must defuse. ### Constraints For all data, $1\le n\le 2\cdot 10^5$, $(sx,sy)\ne(ex,ey)$, and it is guaranteed that for any given coordinate $(x,y)$, we have $x\&y=0$ and $0\le x,y\le 10^{18}$. Subtask 1 (10 pts): It is guaranteed that Mivik can catch his Inner Voice in a straight line (moving only up / down / left / right). Subtask 2 (15 pts): It is guaranteed that $sx=sy=0$. Subtask 3 (20 pts): It is guaranteed that $0\le(\text{any } x,y \text{ coordinate})\le 100$. Subtask 4 (25 pts): It is guaranteed that $n=0$. Subtask 5 (30 pts): No additional constraints. Translated by ChatGPT 5