Island Hopper

You are given a 2D grid where each cell has coordinates in the range \( [0, 1000] \). You start at a point \( (sx, sy) \) and aim to reach the target point \( (tx, ty) \). You can move in the four cardinal directions (up, down, left, right), and each move costs 1 unit of time.

Additionally, there are \( n \) teleportation points provided. Each teleportation point is described by four integers \( inX, inY, outX, outY \). If you are at the coordinate \( (inX, inY) \), you can instantly teleport to \( (outX, outY) \) at zero time cost. You may use these teleportation points optimally to reduce the overall time.

Your task is to determine the minimum time needed to reach \( (tx, ty) \) from \( (sx, sy) \). The problem can be modeled and solved using a breadth-first search (BFS) algorithm.

Note: Movements are only allowed within the grid boundaries and teleportation is only possible if you are exactly at the specified starting position of the teleport.

inputFormat

The input is read from standard input and has the following format:

sx sy tx ty n
inX1 inY1 outX1 outY1
inX2 inY2 outX2 outY2
... (n lines in total)

Here, \( (sx, sy) \) is the starting point, \( (tx, ty) \) is the target, and \( n \) is the number of teleportation points. Each of the following \( n \) lines contains 4 integers separated by spaces that represent a teleportation point.

\(0 \leq sx, sy, tx, ty, inX, inY, outX, outY \leq 1000\)

outputFormat

Output a single integer to standard output representing the minimum time required to reach the target point.

## sample

0 0 10 10 3
1 1 8 8
2 2 3 3
6 6 10 5

6