LatticeLand

LeaperLad wakes in LatticeLand on a disk suspended above a lake of lava. He spots his HeloPak resting on one of the disks; with it, he knows he can escape this trap.

The disks are laid out on a rectangular grid, with one disk at every grid point. The disks are far apart, so from a standing start LeaperLad can only jump to an immediately adjacent disk (up, down, left, or right). Once he is moving, however, he can accelerate.

On each disk he touches, he may do exactly one of the following:

• increase or decrease his speed by $1$ unit in the horizontal direction,
• increase or decrease his speed by $1$ unit in the vertical direction, or
• keep his current speed unchanged.

He may change his speed along only one axis per disk (never both on the same disk). He then jumps by his current velocity vector to the next disk. So, travelling in a straight line from a standing start, he can move $1$, then $2$, then $3$, then $2$, then $1$ unit, and so on.

Because each disk only lets him change his speed along a single axis, he cannot make a diagonal jump from a standstill: he must first build up momentum along one axis before he can add momentum along the other.

Some pairs of disks are joined by walls of fire, which he must never touch. He may get arbitrarily close to a wall, but touching one -- or having a jump graze it -- is fatal. He also must not fall off the edge of the grid.

LeaperLad wants to reach the disk holding his HeloPak and come to a complete stop on it. What is the fewest number of moves this takes?

Each line of input describes one independent scenario as a sequence of space-separated integers.

The first two integers are $w$ and $h$, the width and height of the grid, with $1 \le w \le 64$ and $1 \le h \le 64$. The next two integers are the coordinates of the disk on which LeaperLad wakes, and the two after that are the coordinates of the disk holding the HeloPak. The next integer $f$ is the number of walls of fire, with $0 \le f \le 6$. Then follow $f$ groups of four integers, each giving the coordinates of the two endpoints of one wall.

Every coordinate $(x, y)$ satisfies $0 \le x \le w - 1$ and $0 \le y \le h - 1$. Every wall is at least $1$ unit long. LeaperLad and the HeloPak never start on the same disk, and neither starts on a disk that lies on a wall of fire. There is always a way for LeaperLad to reach the HeloPak.

There are at most $50$ scenarios.

For each scenario, print a single integer: the minimum number of moves LeaperLad needs to reach the HeloPak's disk and stop there.

Every move counts, including a move that only changes his speed without changing his position. For example, decelerating from speed $1$ to speed $0$ while remaining on the same disk still counts as one move -- coming to a complete stop on the destination disk is itself a move.