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 bisect
import heapq
import sys
from types import GeneratorType
from functools import cmp_to_key
from collections import defaultdict, Counter, deque
import math
from functools import lru_cache
from heapq import nlargest
from functools import reduce
import random
from itertools import combinations, permutations
from itertools import accumulate
from operator import xor, add
from operator import mul
from typing import List, Set, Tuple, DefaultDict


inf = float("inf")
PLATFORM = "CF"
if PLATFORM == "LUOGU":
    import numpy as np
    sys.setrecursionlimit(1000000)


class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.size = [1] * n
        self.part = n

    def find(self, x):
        if x != self.root[x]:
            # 在查询的时候合并到顺带直接根节点
            root_x = self.find(self.root[x])
            self.root[x] = root_x
            return root_x
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.size[root_x] >= self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.root[root_x] = root_y
        self.size[root_y] += self.size[root_x]
        # 将非根节点的秩赋0
        self.size[root_x] = 0
        self.part -= 1
        return True

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

    def get_root_part(self):
        # 获取每个根节点对应的组
        part = defaultdict(list)
        n = len(self.root)
        for i in range(n):
            part[self.find(i)].append(i)
        return part

    def get_root_size(self):
        # 获取每个根节点对应的组大小
        size = defaultdict(int)
        n = len(self.root)
        for i in range(n):
            size[self.find(i)] = self.size[self.find(i)]
        return size



class FastIO:
    def __init__(self):
        return

    @staticmethod
    def _read():
        return sys.stdin.readline().strip()

    def read_int(self):
        return int(self._read())

    def read_float(self):
        return float(self._read())

    def read_ints(self):
        return map(int, self._read().split())

    def read_floats(self):
        return map(float, self._read().split())

    def read_ints_minus_one(self):
        return map(lambda x: int(x) - 1, self._read().split())

    def read_list_ints(self):
        return list(map(int, self._read().split()))

    def read_list_floats(self):
        return list(map(float, self._read().split()))

    def read_list_ints_minus_one(self):
        return list(map(lambda x: int(x) - 1, self._read().split()))

    def read_str(self):
        return self._read()

    def read_list_strs(self):
        return self._read().split()

    def read_list_str(self):
        return list(self._read())

    @staticmethod
    def st(x):
        return sys.stdout.write(str(x) + '\n')

    @staticmethod
    def lst(x):
        return sys.stdout.write(" ".join(str(w) for w in x) + '\n')

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def bootstrap(f, queue=[]):
        def wrappedfunc(*args, **kwargs):
            if queue:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        queue.append(to)
                        to = next(to)
                    else:
                        queue.pop()
                        if not queue:
                            break
                        to = queue[-1].send(to)
                return to
        return wrappedfunc


class Solution:
    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        x0, y0, x1, y1 = ac.read_ints()
        n = ac.read_int()
        nodes = set()
        for _ in range(n):
            r, a, b = ac.read_ints()
            for y in range(a, b+1):
                nodes.add((r, y))
        dis = defaultdict(lambda: inf)
        stack = deque([(x0, y0)])
        dis[(x0, y0)] = 0
        while stack:
            x, y = stack.popleft()
            if [x, y] == [x1, y1]:
                break
            for i in range(-1, 2, 1):
                for j in range(-1, 2, 1):
                    a, b = x+i, y+j
                    if (a, b) in nodes and dis[(a, b)] == inf:
                        dis[(a, b)] = dis[(x, y)] + 1
                        stack.append((a, b))
        ans = dis[(x1, y1)]
        ac.st(ans if ans < inf else -1)
        return


Solution().main()