Maze of Inner Voices

Mivik finds himself in an infinite maze with infinitely many rows and columns labeled from \(0\) onward. A cell \((i,j)\) is structurally passable if and only if \(i \& j = 0\) (where \(\&\) denotes the bitwise AND operation in \(\LaTeX\) as \(i\ \&\ j\)). In this maze, his critical inner voice sits still at a fixed location while Mikiv tries to reach it. However, the evil ggy has planted bombs on some of the passable cells. In order to step on a cell containing one or more bombs, Mikiv must first remove all bombs on that cell. (Note that bombs might overlap, and removing them requires a single action per cell with bombs.)

Given the starting coordinates of Mikiv and the fixed location of his inner voice, determine the minimum number of cells Mikiv must traverse (excluding his starting cell) to catch his inner voice, assuming he can only move in the four cardinal directions (up, down, left, right) and he may only step onto a cell \((i,j)\) if \(i \& j = 0\). Also, under the condition of using the minimum number of steps, output which bombed cells must have their bombs removed. It is guaranteed that no bomb is placed at Mikiv's starting cell.

Input Format: The input begins with a line containing four integers \(sx\), \(sy\), \(tx\), \(ty\), representing the row and column coordinates of Mikiv's starting cell and the inner voice's cell respectively. The next line contains an integer \(n\) denoting the number of bomb placements. Each of the following \(n\) lines contains two integers \(x\) and \(y\) indicating that a bomb is placed at cell \((x,y)\). You may assume that all bomb positions (\(x,y\)) satisfy \(x \& y = 0\) and that \(sx,sy \ge 0\); also, bombs are never placed at the starting cell.

Movement: Mikiv can move from cell \((x,y)\) to any of its four adjacent cells \((x+1,y)\), \((x-1,y)\), \((x,y+1)\), or \((x,y-1)\) as long as the destination cell satisfies \(\, i \& j = 0\) and has been cleared of bombs if bombs are present.

Output Format: If there exists a path from the starting cell to the inner voice's cell, output the minimum number of cells (steps) traversed (excluding the starting cell) on the first line. On the second line, output an integer \(k\) representing how many cells along this shortest path contain bombs (and hence must have their bombs removed). Then output \(k\) lines each containing two integers representing the coordinates of these bombed cells, in the order they are encountered along the path. If the inner voice is unreachable, output -1.

Note: The cells that are normally passable are those satisfying \(i \& j = 0\); bomb removal does not count as an extra step. All moves cost 1 step regardless of whether bombs are removed on the destination cell.

inputFormat

The first line contains four space-separated integers: \(sx\), \(sy\), \(tx\), \(ty\). The second line contains an integer \(n\) (\(n \ge 0\)) indicating the number of bomb placements. Each of the following \(n\) lines contains two space-separated integers \(x\) and \(y\), denoting a bomb is placed at cell \((x,y)\).

outputFormat

If a path exists, the output should consist of the following:

• The first line contains a single integer representing the minimum number of cells (steps) traversed (excluding the starting cell).
• The second line contains an integer \(k\) (\(k \ge 0\)) indicating the number of bombed cells that must be cleared along this path.
• Then, \(k\) lines follow, each containing two space-separated integers \(x\) and \(y\) representing a bombed cell (in the order encountered along the chosen path).

If no valid path exists, output a single line with -1.

sample

1 2 3 4
1
1 4

6
1
1 4