The black king is standing on a chess field consisting of 10^9 rows and 10^9 columns. We will consider the rows of the field numbered with integers from 1 to 10^9 from top to bottom. The columns are similarly numbered with integers from 1 to 10^9 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_{i}, a_{i}, b_{i} (a_{i} ≤ b_{i}), denoting that cells in columns from number a_{i} to number b_{i} inclusive in the r_{i}-th row are allowed.

Your task is to find the minimum number of moves the king needs to get from square (x_0, y_0) to square (x_1, y_1), 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.


-----Input-----

The first line contains four space-separated integers x_0, y_0, x_1, y_1 (1 ≤ x_0, y_0, x_1, y_1 ≤ 10^9), denoting the initial and the final positions of the king.

The second line contains a single integer n (1 ≤ n ≤ 10^5), 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_{i}, a_{i}, b_{i} (1 ≤ r_{i}, a_{i}, b_{i} ≤ 10^9, a_{i} ≤ b_{i}), denoting that cells in columns from number a_{i} to number b_{i} inclusive in the r_{i}-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^5.


-----Output-----

If there is no path between the initial and final position along allowed cells, print -1.

Otherwise print a single integer — the minimum number of moves the king needs to get from the initial position to the final one.


-----Examples-----
Input
5 7 6 11
3
5 3 8
6 7 11
5 2 5

Output
4

Input
3 4 3 10
3
3 1 4
4 5 9
3 10 10

Output
6

Input
1 1 2 10
2
1 1 3
2 6 10

Output
-1

Difficulty: interview

Starter code:

Solutions:
import sys
from collections import deque

def solve():
    xadj, yadj = [0, 0, - 1, 1, -1, -1, 1, 1], [1, -1, 0, 0, -1, 1, -1, 1]
    x0, y0, x1, y1, = rv()
    n, = rv()
    good = set()
    visited = dict()
    for seg in range(n):
        r, a, b, = rv()
        for c in range(a, b + 1): good.add((r, c))
    points = deque()
    points.append((x0, y0, 0))
    visited[(x0, y0)] = 0
    while len(points) > 0:
        cur = points.popleft()
        for i in range(8):
            pos = (cur[0] + xadj[i], cur[1] + yadj[i])
            if pos in good and pos not in visited:
                points.append((pos[0], pos[1], cur[2] + 1))
                visited[pos] = cur[2] + 1
    print(visited[(x1, y1)] if (x1, y1) in visited else - 1)







def prt(l): return print(''.join(l))
def rv(): return map(int, input().split())
def rl(n): return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()

import sys
from collections import deque

def solve():
    xadj, yadj = [0, 0, - 1, 1, -1, -1, 1, 1], [1, -1, 0, 0, -1, 1, -1, 1]
    x0, y0, x1, y1, = rv()
    n, = rv()
    good = set()
    visited = dict()
    for seg in range(n):
        r, a, b, = rv()
        for c in range(a, b + 1): good.add((r, c))
    points = deque()
    points.append((x0, y0, 0))
    visited[(x0, y0)] = 0
    while len(points) > 0:
        cur = points.popleft()
        for i in range(8):
            pos = (cur[0] + xadj[i], cur[1] + yadj[i])
            if pos in good and pos not in visited:
                points.append((pos[0], pos[1], cur[2] + 1))
                visited[pos] = cur[2] + 1
    print(visited[(x1, y1)] if (x1, y1) in visited else - 1)







def prt(l): return print(''.join(l))
def rv(): return map(int, input().split())
def rl(n): return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()

from collections import deque
x0, y0, x1,y1 = map(int, input().split())
n = int(input())
g = {}
for _ in range(n):
    r,a,b = map(int, input().split())
    for i in range(a,b+1):
        g[(r,i)] = -1
g[(x0,y0)] = 0
q = deque([(x0,y0)])
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
while len(q) > 0:
    c = q.popleft()
    for i in range(8):
        m = (c[0]+dx[i], c[1]+dy[i])
        if m in g and g[m] == -1:
            q.append(m)
            g[m] = g[c]+1
    
print(g[(x1,y1)])
return

from collections import deque

x0, y0, x1, y1 = list(map(int, input().split()))
n = int(input())

bars = {}
for i in range(n):
    r, a, b = list(map(int, input().split()))
    if r not in bars:
        bars[r] = {}
    for j in range(a, b+1):
        bars[r][j] = -1

bars[x0][y0] = 0
q = deque()
q.append(tuple([x0, y0]))

while q:
    node = q.popleft()

    for i in range(-1, 2):
        row = node[0] + i
        if row not in bars:
            continue

        for j in range(-1, 2):
            col = node[1] + j
            if col not in bars[row] or (i == 0 and j == 0):
                continue

            if bars[row][col] == -1:
                bars[row][col] = bars[node[0]][node[1]] + 1
                q.append(tuple([row, col]))

    if bars[x1][y1] != -1:
        break

print(bars[x1][y1])


from collections import defaultdict

x0, y0, x1, y1 = [int(c) for c in input().split()]
n = int(input())

allowed = defaultdict(set)
for _ in range(n):
    row, col_x, col_y = [int(c) for c in input().split()]
    for c in range(col_x, col_y+1):
        allowed[row].add(c)

start, end = (x0, y0), (x1, y1)
if start == end:
    print(0)
    return

queue = [start]
visited = {start}

neighbors = []
for i in range(-1, 2):
    for j in range(-1, 2):
        if not (i == 0 and j == 0):
            neighbors.append((i, j))

ans = 1
while queue:
    new_queue = []
    for pos in queue:
        for neigh in neighbors:
            cur = pos[0] + neigh[0], pos[1] + neigh[1]
            if cur == end:
                print(ans)
                return
            if 1 <= cur[0] <= 10**9 and 1 <= cur[1] <= 10**9:
                if cur[0] in allowed and cur[1] in allowed[cur[0]]:
                    if cur not in visited:
                        visited.add(cur)
                        new_queue.append(cur)

    ans += 1
    queue = new_queue

print(-1)


from collections import deque

px1, py1, px2, py2 = [int(x) for x in input().split()]
p_start, p_end = (px1, py1), (px2, py2)
n = int(input())
valid = set()
for _ in range(n):
    r, a, b = [int(x) for x in input().split()]
    valid.update(((r, j) for j in range(a, b + 1)))

d = deque()
d.append((p_start, 0))
visited = {p_start}
while d:
    p1, m = d.popleft()
    if p1 == p_end:
        print(m)
        quit()
    for p2 in [(p1[0] + dx, p1[1] + dy) for dx in [-1, 0, 1] for dy in [-1, 0, 1]]:
        if (p2 in valid) and (p2 not in visited):
            visited.add(p2)
            d.append((p2, m + 1))
            
            

print(-1)


from collections import deque

x_start, y_start, x_end, y_end = [int(x) for x in input().split()]
n = int(input())
moves = {}
for _ in range(n):
    r, a, b = [int(x) for x in input().split()]
    for j in range(a, b + 1):
        moves[(r, j)] = -1

p_start = x_start, y_start
d = deque([p_start])
moves[p_start] = 0
while d:
    x1, y1 = d.popleft()
    m = moves[(x1, y1)]
    for p2 in [(x1 + dx, y1 + dy) for dx in [-1, 0, 1] for dy in [-1, 0, 1]]:
        if (p2 in moves) and (moves[p2] == -1):
            d.append(p2)
            moves[p2] = m + 1
            
print(moves[(x_end, y_end)])


def bfs(a,b):
  nonlocal segment
  q = [(a,b)]
  while q:
    a, b = q.pop(0) 
    x = [0,0,-1,1,-1,1,-1,1]
    y = [1,-1,0,0,-1,1,1,-1]
    for i in range(8):
      a_new, b_new = a+x[i], b+y[i]
      if (a_new,b_new) in segment and segment[(a_new,b_new)] == -1:
        segment[(a_new,b_new)] = segment[(a,b)] + 1
        q.append((a_new,b_new))


x_start, y_start, x_end, y_end = list(map(int, input().split()))
n = int(input())
segment = {}
for i in range(n):
  r, a, b = list(map(int,input().split()))
  for i in range(a,b+1):
    segment[(r,i)] = -1
if (x_end,y_end) not in segment:
  print(-1)
  quit()
segment[(x_start,y_start)] = 0
bfs(x_start,y_start)
print(segment[(x_end,y_end)])




# ip = open("testdata.txt", "r")

# def input():
# 	return ip.readline().strip()

from collections import deque, defaultdict

x0, y0, x1, y1 = map(int, input().split())

allowed = defaultdict(list)
allowed[x0].append([y0, y0])
allowed[x1].append([y1, y1])

m = int(input())

for _ in range(m):
	r, a, b = map(int, input().split())
	allowed[r].append([a, b])

def get_valid_moves(x, y):
	valid_pos = set()
	if x in allowed:
		for l, r in allowed[x]:
			if l <= y-1 <= r:
				valid_pos.add((x, y-1))
			if l <= y+1 <= r:
				valid_pos.add((x, y+1))
	if x-1 in allowed:
		for l, r in allowed[x-1]:
			if l <= y-1 <= r:
				valid_pos.add((x-1, y-1))
			if l <= y <= r:
				valid_pos.add((x-1, y))
			if l <= y+1 <= r:
				valid_pos.add((x-1, y+1))
	if x+1 in allowed:
		for l, r in allowed[x+1]:
			if l <= y-1 <= r:
				valid_pos.add((x+1, y-1))
			if l <= y <= r:
				valid_pos.add((x+1, y))
			if l <= y+1 <= r:
				valid_pos.add((x+1, y+1))
	return valid_pos

def bfs():
	nonlocal x0, y0, x1, y1
	dq = deque([(x0, y0)])
	vis_set = {(x0, y0), }
	level = defaultdict(int)
	while dq:
		x0, y0 = dq.popleft()
		for x, y in get_valid_moves(x0, y0):
			if not (x, y) in vis_set:
				level[(x, y)] = level[(x0, y0)] + 1
				if (x, y)==(x1, y1):
					return level[(x, y)]
				vis_set.add((x, y))
				dq.append((x, y))
	return -1

ans = bfs()
print(ans)

limit = 10**9
mark = set()
dist = {}
dx = [0, 0, 1, -1, 1, -1, 1, -1]
dy = [1, -1, 0, 0, 1, -1, -1, 1]

def calc(x, y):
    nonlocal limit
    val = x
    val = val * limit + y
    return val

def bfs():
    nonlocal x0, y0, x1, y1, mark, dist, dx, dy
    myqueue = []
    S = calc(x0, y0)
    myqueue.append(S)
    dist[S] = 0

    while myqueue:
        u = myqueue.pop(0)
        x = u // limit
        y = u % limit

        for i in range(8):
            xx = x + dx[i]
            yy = y + dy[i]
            v = calc(xx, yy)
            if (1 <= xx <= limit and 1 <= yy <= limit and v in mark):
                if v not in dist:
                    dist[v] = dist[u] + 1
                    if v == calc(x1, y1):
                        print(dist[v])
                        return
                    myqueue.append(v)

    print(-1)

x0, y0, x1, y1 = list(map(int, input().split()))
mark.add(calc(x0, y0))
mark.add(calc(x1, y1))

n = int(input())

for i in range(1, n+1):
    r, a, b = list(map(int, input().split()))
    for j in range(a, b+1):
        mark.add(calc(r, j))

bfs()


def main():
    import sys
    from collections import deque
    x0,y0,x1,y1 = map(int,input().strip().split())
    n = int(input())
    S = list(map(int,sys.stdin.read().strip().split()))
    h = set()
    d = {}
    
    def getchild(a):
        c = []
        xc = [1,-1,0,0,1,1,-1,-1]
        yc = [0,0,1,-1,1,-1,1,-1]
        for i in range(8):
            if ((a[0]+xc[i],a[1]+yc[i]) in h):
                c.append((a[0]+xc[i],a[1]+yc[i]))
        return(c)
        
    
    class g:
        def __init__(self):
            self.depth = -1
            self.child = []
        
    for i in range(0,3*n,3):
        r,a,b = S[i],S[i+1],S[i+2]
        for j in range(a,b+1):
            h.add((r,j))
            d[(r,j)] = g()
    king = d[(x0,y0)]
    destination = d[(x1,y1)]
    for i in h:
        d[i].child = getchild(i)
        
    Q = deque()
    Q.append(king)
    king.depth = 0
    while(len(Q)>0):
        a = Q.popleft()
        for i in a.child:
            if d[i].depth==-1:
                Q.append(d[i])
                d[i].depth=a.depth+1
        if a==destination:
            break
    print(destination.depth)

main()

# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 2/11/20

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List


def solve(x0, y0, x1, y1, N, A):
    points = set()
    for y, xl, xr in A:
        for x in range(xl, xr+1):
            points.add((x, y))
    dist = collections.defaultdict(int)
    
    q = [(x0, y0)]
    while q:
        nq = []
        for x, y in q:
            d = dist[x, y] + 1
            for ny in range(y-1, y+2):
                for nx in range(x-1, x+2):
                    if (nx, ny) in points and (dist[nx, ny] == 0 or dist[nx, ny] > d):
                        dist[nx, ny] = d
                        nq.append((nx, ny))
        q = nq
        
    # print(dist)
    # print(points)
        
    ans = dist[x1, y1]
    return ans if ans != 0 else -1
    
    
    
    
    
    
    
    
    

y0, x0, y1, x1 = map(int, input().split())
N = int(input())
A = []
for i in range(N):
    y, xl, xr = map(int, input().split())
    A.append((y, xl, xr))
    
print(solve(x0, y0, x1, y1, N, A))

'''
http://codeforces.com/contest/242/problem/C
'''
from collections import defaultdict
from heapq import heappush, heappop
INF = int(1e9)

def BFS(x0,y0,x1,y1, graph):
    heap_stack = [[0,x0,y0]]
    visited = set()
    while heap_stack:
        distance, currentX, currentY = heappop(heap_stack)
        if currentX == x1 and currentY == y1: return distance
        for dx, dy in [[1,0],[-1,0],[0,1],[0,-1],[-1,-1],[-1,1],[1,-1],[1,1]]:
            newX, newY = currentX+dx, currentY+dy
            if 1 <= newX <= INF and 1 <= newY <= INF and newY in graph[newX] and (newX, newY) not in visited:
                visited.add((newX, newY))
                heappush(heap_stack, [distance+1, newX, newY])
    return -1

x0,y0,x1,y1 = list(map(int, input().strip().split(" ")))
number_of_allowed_cells = int(input())
graph = defaultdict(set)
for i in range(number_of_allowed_cells):
    row, column1, column2 = list(map(int, input().strip().split(" ")))
    allowed_column = set(range(column1,column2+1))
    graph[row] = graph[row].union(allowed_column)
print(BFS(x0,y0,x1,y1,graph))
                


from collections import deque

x0,y0,x1,y1 = list(map(int, input().split()))
n = int(input())
allowed = {}
for i in range(n):
    r,a,b = list(map(int, input().split()))
    for j in range(a,b+1):
        allowed[(r,j)] = True

visited = {}
q = deque()
q.append((x0, y0))
visited[(x0, y0)] = 0
dir = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
result = -1
while len(q) > 0:
    x,y = q.popleft()
    original_dist = visited[(x, y)]
    if x == x1 and y == y1:
        result = original_dist
        break
    for i in range(len(dir)):
        dx, dy = dir[i]
        nx, ny = x+dx, y+dy
        if (nx, ny) in allowed and (nx, ny) not in visited:
            q.append((nx,ny))
            visited[(nx, ny)] = original_dist + 1
print(result)



from collections import deque

x0,y0,x1,y1=list(map(int, input().split()))
n=int(input())
allowed={}
for i in range(n):
    r,a,b=list(map(int,input().split()))
    for j in range(a,b+1):
        allowed[(r,j)]=True
visited={}
q=deque()
q.append((x0,y0))
visited[(x0,y0)]=0
dire=[(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,1),(1,-1)]
result=-1;
while len(q)>0:
    x,y=q.popleft()
    original_dist=visited[(x,y)]
    if x==x1 and y==y1:
        result=original_dist;
        break;
    for i in range(len(dire)):
        dx,dy=dire[i]
        nx,ny=x+dx,y+dy
        if (nx,ny) in allowed and (nx,ny) not in visited:
            q.append((nx,ny))
            visited[(nx,ny)]=original_dist+1
print(result)            


from collections import deque  

x0,y0,x1,y1 = list(map(int, input().split()))
n=int(input())
allowed= {}
for i in range(n):
    r,a,b=list(map(int, input().split()))
    for j in range(a,b+1):
        allowed[(r,j)]=True


visited={}
q=deque()
q.append((x0,y0))
visited[(x0,y0)]=0
dir = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
result=-1
while len(q)>0:
    x,y=q.popleft()
    original_dist=visited[x,y]
    if x==x1 and y==y1:
        result = original_dist
        break
    for i in range(len(dir)):
        dx,dy=dir[i]
        nx,ny =x+dx, y+dy
        if (nx,ny) in allowed and (nx,ny) not in visited:
            q.append((nx,ny))
            visited[(nx,ny)]=original_dist+1
print(result)



from collections import deque, defaultdict


class Solution:

    def solve(self):
        kpos = input().split()
        kpos = [int(x) for x in kpos]
        startK = [kpos[0], kpos[1]]
        endK = [kpos[2], kpos[3]]
        N = int(input())

        intervals_dict = defaultdict(list)
        for _ in range(N):
            allowed = input().split()
            allowed = [int(x) for x in allowed]
            row, start, end = allowed
            intervals_dict[row].append([start, end])

        # merge intervals
        for row in intervals_dict:
            intervals = intervals_dict[row]
            intervals.sort()
            final_merged = []

            last_start, last_end = intervals[0]
            for interval in intervals[1:]:
                start, end = interval
                if start <= last_end:
                    last_end = end
                    continue
                final_merged.append([last_start, last_end])
                last_start = start
                last_end = end

            final_merged.append([last_start, last_end])
            last_start = start
            intervals_dict[row] = final_merged

        # BFS
        queue = deque([startK])
        moves = 0
        seen = set((startK[0], startK[1]))
        directions = [(i, j) for i in [1, 0, -1]
                      for j in [1, 0, -1] if not(i == j == 0)]

        def get_intervals(intervals_dict):
            for intervals in intervals_dict:
                yield intervals

        while queue:
            moves += 1
            for i in range(len(queue)):
                x, y = queue.popleft()

                for dx, dy in directions:
                    row, col = x + dx, y + dy

                    if row in intervals_dict and (row, col) not in seen:
                        valid = False
                        for interval in intervals_dict[row]:
                            start_int, end_int = interval
                            if start_int <= col <= end_int:
                                valid = True
                                break
                        if valid:
                            intervals_dict[row][0][0] <= col <= intervals_dict[row][0][1]
                            seen.add((row, col))
                            if (row, col) == (endK[0], endK[1]):
                                return moves
                            queue.append((row, col))

        return -1


soln = Solution()
print(soln.solve())



def main():

    import sys, math
    #from bisect import bisect_left as bl, bisect_right as br, insort
    from heapq import heapify, heappush, heappop
    from collections import defaultdict as dd, deque, Counter
    #from itertools import permutations,combinations
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    x0,y0,x1,y1=mdata()
    n=int(data())
    d=dd(int)
    for i in range(n):
        r,a,b=mdata()
        for i in range(a,b+1):
            d[(r,i)]=1
    if d[(x0,y0)]==0:
        print(-1)
        return

    dist = dd(int)
    for i in d:
        dist[i]=INF
    dist[(x0,y0)] = 0
    vis = dd(int)
    s = []
    heapify(s)
    heappush(s, (0, x0,y0))

    while len(s) != 0:
        wei, x,y = heappop(s)
        vis[(x,y)] = 1

        for i in [-1,0,1]:
            for j in [-1,0,1]:
                if i==j==0:
                    continue
                if d[(x+i,y+j)]==1:
                    if dist[(x,y)] + 1 < dist[(x+i,y+j)]:
                        dist[(x+i,y+j)] = dist[(x,y)] + 1
                        if vis[(x+i,y+j)] == 0:
                            heappush(s, (dist[(x+i,y+j)], x+i,y+j))
    if dist[x1,y1]==INF:
        print(-1)
    else:
        print(dist[x1,y1])


def __starting_point():
    main()

__starting_point()