The black king is standing on a chess field consisting of 10<sup class="upper-index">9</sup> rows and 10<sup class="upper-index">9</sup> columns. We will consider the rows of the field numbered with integers from 1 to 10<sup class="upper-index">9</sup> from top to bottom. The columns are similarly numbered with integers from 1 to 10<sup class="upper-index">9</sup> from left to right. We will denote a cell of the field that is located in the *i*-th row and *j*-th column as (*i*, *j*).

You know that some squares of the given chess field are allowed. All allowed cells of the chess field are given as *n* segments. Each segment is described by three integers *r*<sub class="lower-index">*i*</sub>, *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (*a*<sub class="lower-index">*i*</sub> ≤ *b*<sub class="lower-index">*i*</sub>), denoting that cells in columns from number *a*<sub class="lower-index">*i*</sub> to number *b*<sub class="lower-index">*i*</sub> inclusive in the *r*<sub class="lower-index">*i*</sub>-th row are allowed.

Your task is to find the minimum number of moves the king needs to get from square (*x*<sub class="lower-index">0</sub>, *y*<sub class="lower-index">0</sub>) to square (*x*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">1</sub>), provided that he only moves along the allowed cells. In other words, the king can be located only on allowed cells on his way.

Let us remind you that a chess king can move to any of the neighboring cells in one move. Two cells of a chess field are considered neighboring if they share at least one point.
The first line contains four space-separated integers *x*<sub class="lower-index">0</sub>, *y*<sub class="lower-index">0</sub>, *x*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">1</sub> (1 ≤ *x*<sub class="lower-index">0</sub>, *y*<sub class="lower-index">0</sub>, *x*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">1</sub> ≤ 10<sup class="upper-index">9</sup>), denoting the initial and the final positions of the king.

The second line contains a single integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>), denoting the number of segments of allowed cells. Next *n* lines contain the descriptions of these segments. The *i*-th line contains three space-separated integers *r*<sub class="lower-index">*i*</sub>, *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> (1 ≤ *r*<sub class="lower-index">*i*</sub>, *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>, *a*<sub class="lower-index">*i*</sub> ≤ *b*<sub class="lower-index">*i*</sub>), denoting that cells in columns from number *a*<sub class="lower-index">*i*</sub> to number *b*<sub class="lower-index">*i*</sub> inclusive in the *r*<sub class="lower-index">*i*</sub>-th row are allowed. Note that the segments of the allowed cells can intersect and embed arbitrarily.

It is guaranteed that the king's initial and final position are allowed cells. It is guaranteed that the king's initial and the final positions do not coincide. It is guaranteed that the total length of all given segments doesn't exceed 10<sup class="upper-index">5</sup>.

import operator, sys





from collections import deque

def bfs(G, source):
    """Modifies vertices within graph G without returning
    anything."""
    for v in G:
        v.dist = float("inf")
        v.prev = None
    source.dist = 0

    q = deque([source])
    while len(q):
        u = q.popleft()
        for v in u.get_neighbors():
            if v.dist == float("inf"):
                v.dist = u.dist + 1
                v.prev = u
                q.append(v)





class Vertex:
    """A vertex that maintains a dict of (vertex -> weight)
    key-value pairs of neighbors to which it is connected.
    This avoids needing an extra data type, EDGE, to represent
    connections between vertices."""
    def __init__(self, node):
        self.node = node
        self.adjacent = {}

    def __str__(self):
        return str(self.node)

    def __repr__(self):
        """Override this to print a string representation of
        this object."""
        return str(self.node)

    def get_node(self):
        return self.node

    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight

    def get_neighbors(self):
        return self.adjacent.keys()

    def get_weight(self, neighbor):
        return self.adjacent[neighbor]

class UnweightedVertex(Vertex):
    """A vertex that maintains a list of vertices to which it is connected,
    instead of a dict with vertices and their corresponding weights."""
    def __init__(self, node):
        self.node = node
        self.adjacent = []

    def add_neighbor(self, neighbor):
        self.adjacent.append(neighbor)

    def get_neighbors(self):
        return self.adjacent



class Graph:
    """A collection of vertices connected by edges
    to their neighbors. The vertices are maintained
    in a dict of (node -> vertex) key-value pairs."""
    def __init__(self):
        self.vertices = {}

    def __iter__(self):
        """Returns all vertex instances in vertices dict."""
        return iter(self.vertices.values())

    def add_vertex(self, node):
        new_vertex = Vertex(node)
        self.vertices[node] = new_vertex
        return new_vertex

    # returns keys instead of values
    def get_nodes(self):
        return iter(self.vertices.keys())

    def get_vertex(self, node):
        try:
            return self.vertices[node]
        except:
            return None

    def size(self):
        return len(self.vertices)

    def has_vertex(self, node):
        return node in self.vertices

    def add_edge(self, frm, to, cost=0, both=False):
        if frm not in self.vertices:
            self.add_vertex(frm)
        if to not in self.vertices:
            self.add_vertex(to)

        self.vertices[frm].add_neighbor(self.vertices[to], cost)
        if both:
            self.vertices[to].add_neighbor(self.vertices[frm], cost)

class UnweightedGraph(Graph):
    """UnweightedVertex instances are stored instead of Vertex instances."""
    def add_vertex(self, node):
        new_vertex = UnweightedVertex(node)
        self.vertices[node] = new_vertex
        return new_vertex

    def add_edge(self, frm, to, both=False):
        if frm not in self.vertices:
            self.add_vertex(frm)
        if to not in self.vertices:
            self.add_vertex(to)

        self.vertices[frm].add_neighbor(self.vertices[to])
        if both:
            self.vertices[to].add_neighbor(self.vertices[frm])










g = UnweightedGraph()

with open(sys.argv[1]) as f:
    lines = f.readlines()
f.close()

ll = []
for line in lines:
    ll.append(list(map(int, line.split(' '))))

start = (ll[0][0], ll[0][1])
end = (ll[0][2], ll[0][3])

for i in range(2, len(ll)):
    l = ll[i]
    for col in range(l[1], l[2]+1):
        g.add_vertex((l[0], col))



def get_adjacent(node):
    return [
        tuple(map(operator.add, node, adj)) for adj in
        [(-1, -1), (-1, 0), (-1, 1), (0, -1),
        (0, 1), (1, -1), (1, 0), (1, 1)]
    ]

for v in g.get_nodes():
    for u in get_adjacent(v):
        if g.has_vertex(u):
            g.add_edge(v, u)


bfs(g, g.get_vertex(start))
dist = g.get_vertex(end).dist
print(-1 if dist == float("inf") else dist)



