Problem Description

Mivik sees his Inner Voice in a mirror-like symmetrical maze. This maze is special: it has an infinite number of rows and columns, both numbered starting from 0. A cell \((i, j)\) is passable (no obstacle) if and only if \((i \& j) = 0\), where \(\&\) denotes the bitwise AND operation. The image below shows the maze for rows and columns from 0 to 63:

Mivik wants to catch and eliminate the Inner Voice that gives him negative thoughts, but he is lost. Mivik and the Inner Voice are initially at two points in the maze. Mivik wants to know the minimum number of cells he needs to traverse to catch his Inner Voice (excluding the starting cell).

However, the game is not as simple as Mivik imagines. The evil ggy has placed many bombs in some cells of the maze, and Mivik needs to disarm them to step on these cells. Mivik needs you to tell him, in the scenario where he walks the least number of cells, which bombs he must disarm at a minimum.

Note that bombs may overlap, and you must disarm all bombs on a cell to pass it. Bombs are guaranteed not to overlap with the starting point.

Input Format

The first line contains an integer \(n\), representing the number of bombs set by ggy.

The next \(n\) lines, each containing two non-negative integers, represent the coordinates of the \(i\)-th bomb (numbered from 1).

The next line contains two non-negative integers \(sx\) and \(sy\), representing the row and column where Mivik is located.

The next line contains two non-negative integers \(ex\) and \(ey\), representing the row and column where Mivik's Inner Voice is located.

Output Format

The first line contains an integer representing the minimum number of cells Mivik needs to traverse to catch his Inner Voice.

The next line contains a 01 string of length \(n\), where the \(i\)-th character is 1 if Mivik must disarm the \(i\)-th bomb, and 0 if not.

Sample Input and Output

Sample Input #1

0
0 0
0 2

Sample Output #1

2

Sample Input #2

3
0 0
0 2
1 2
4 2
3 4

Sample Output #2

13
110

Sample Input #3

0
12 34
3 100

Sample Output #3

85

Notes

Sample Explanation

Sample 1: 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 image below:

The top-left corner of the image is \((0,0)\), blue represents Mivik's starting position, green represents the Inner Voice's position, red represents Mivik's shortest path, yellow represents bombs, and orange (yellow + red) represents the bombs Mivik must disarm.

Data Range

For all data, \(1 \leq n \leq 2 \cdot 10^5\), \((sx, sy) \neq (ex, ey)\), and for any given coordinates \((x, y)\), \(x \& y = 0\) and \(0 \leq x, y \leq 10^{18}\).

Subtask 1 (10 pts): Guaranteed that Mivik can catch his Inner Voice in a straight line (only moving up/down/left/right).

Subtask 2 (15 pts): Guaranteed that \(sx = sy = 0\).

Subtask 3 (20 pts): Guaranteed that \(0 \leq (\text{any x, y coordinates}) \leq 100\).

Subtask 4 (25 pts): Guaranteed that \(n = 0\).

Subtask 5 (30 pts): No special restrictions.

见题面 Input 部分

见题面 Output 部分