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: MEDIUM_HARD
Tags: String algorithms

Graph algorithms

Graph traversal

Shortest paths

Starter code:

Solutions:
from collections import deque
(x_0, y_0, x_1, y_1) = list(map(int, input().split()))
n = int(input())
g = {}
for _ in range(n):
	(r, a, b) = list(map(int, input().split()))
	for i in range(a, b + 1):
		g[r, i] = -1
g[x_0, y_0] = 0
q = deque([(x_0, y_0)])
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
while len(q) != 0:
	current = q.popleft()
	for i in range(8):
		neigbor = (current[0] + dx[i], current[1] + dy[i])
		if neigbor in g and g[neigbor] == -1:
			q.append(neigbor)
			g[neigbor] = g[current] + 1
		if neigbor == (x_1, y_1):
			break
print(g[x_1, y_1])


(x0, y0, x1, y1) = map(int, input().split())
n = int(input())
valid = set()
for _ in range(n):
	(r, a, b) = map(int, input().split())
	for x in range(a, b + 1):
		valid.add((r, x))
(visited, moves, neighbors) = ({(x0, y0)}, 0, [(x0, y0)])
while neighbors:
	(current, neighbors) = (neighbors, [])
	for (x, y) in current:
		if (x, y) == (x1, y1):
			print(moves)
			exit()
		else:
			for (p, q) in ((x + 1, y), (x, y + 1), (x + 1, y + 1), (x - 1, y), (x, y - 1), (x - 1, y - 1), (x - 1, y + 1), (x + 1, y - 1)):
				if (p, q) in valid and (p, q) not in visited:
					neighbors.append((p, q))
					visited.add((p, q))
	moves += 1
print(-1)


from collections import defaultdict
from heapq import heappush, heappop
INF = int(1000000000.0)

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 *
import bisect
import heapq
import sys
from math import inf

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def isPossiblePlace(x, y):
	for my_list in allowed[x]:
		(a, b) = my_list
		if y >= a and y <= b:
			return True
	return False

def bfs(x0, y0, x1, y1):
	visited = defaultdict(list)
	to_visit = deque()
	to_visit.append((x0, y0, 0))
	visited[x0].append(y0)
	while to_visit:
		(x, y, d) = to_visit.popleft()
		for dx in [-1, 0, 1]:
			for dy in [-1, 0, 1]:
				if abs(dx) + abs(dy) != 0:
					nx = x + dx
					ny = y + dy
				if nx >= 1 and nx <= 10 ** 9 and (ny >= 1) and (ny <= 10 ** 9):
					if isPossiblePlace(nx, ny):
						if (nx, ny) == (x1, y1):
							return d + 1
						if ny not in visited[nx]:
							visited[nx].append(ny)
							to_visit.append((nx, ny, d + 1))
	return -1
(x0, y0, x1, y1) = rl()
n = ri()
allowed = defaultdict(set)
for _ in range(n):
	(i, start, end) = rl()
	allowed[i].add((start, end))
print(bfs(x0, y0, x1, y1))


def main():
	import sys, math
	from heapq import heapify, heappush, heappop
	from collections import defaultdict as dd, deque, Counter

	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)
	INF = int(1000000000.0)
	mod = int(1000000000.0) + 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()


from sys import stdin, stdout
import time, math
from collections import defaultdict

def pn(ob):
	stdout.write(str(ob))

def inp():
	return stdin.readline()

def fpow(n, p):
	if p == 1:
		return n
	if p & 1 == 1:
		return n * fpow(n, p - 1)
	else:
		return fpow(n, p / 2) * fpow(n, p / 2)

def def_val():
	return False

def def_dist():
	return math.inf
valid = defaultdict(def_val)
dist = defaultdict(def_dist)
dx = (-1, 0, 1, 0, 1, 1, -1, -1)
dy = (0, 1, 0, -1, 1, -1, 1, -1)

def bfs(x, y, dest):
	q = []
	q.append((x, y))
	valid[x, y] = False
	dist[x, y] = 0
	while len(q) > 0:
		coords = q.pop(0)
		for k in range(0, 8, 1):
			x = coords[0] + dx[k]
			y = coords[1] + dy[k]
			new_coords = (x, y)
			dist[new_coords] = min(dist[coords] + 1, dist[new_coords])
			if valid[new_coords]:
				valid[new_coords] = False
				q.append(new_coords)
	if dist[dest] == math.inf:
		pn(-1)
	else:
		pn(dist[dest])

def process():
	(x0, y0, x1, y1) = map(int, input().split())
	n = int(inp())
	for i in range(0, n, 1):
		(r, a, b) = map(int, input().split())
		for j in range(a, b + 1, 1):
			valid[r, j] = True
	bfs(x0, y0, (x1, y1))

def main():
	t = 1
	process()
main()


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

def I():
	return list(map(int, input().split()))
dic = {}
(x0, y0, x1, y1) = I()
for i in range(int(input())):
	(r, a, b) = I()
	while a != b + 1:
		tup = (r, a)
		dic[tup] = -1
		a += 1
x = [-1, -1, -1, 0, 0, 1, 1, 1]
y = [-1, 0, 1, -1, 1, -1, 0, 1]
dic[x0, y0] = 0
queue = deque([(x0, y0)])
while len(queue) > 0:
	popped = queue.popleft()
	for i in range(8):
		new_square = (popped[0] + x[i], popped[1] + y[i])
		if new_square in dic and dic[new_square] == -1:
			queue.append(new_square)
			dic[new_square] = dic[popped] + 1
print(dic[x1, y1])


from collections import deque, defaultdict

def bfs(x, y, x_dest, y_dest, allowed):
	visit_time = dict()
	fringe = deque()
	fringe.append((x, y))
	visit_time[x, y] = 0
	while len(fringe):
		(x, y) = fringe.popleft()
		if (x, y) == (x_dest, y_dest):
			return visit_time[x, y]
		for i in range(-1, 2):
			for j in range(-1, 2):
				if (x + i, y + j) not in visit_time and allowed[x, y]:
					fringe.append((x + i, y + j))
					visit_time[x + i, y + j] = visit_time[x, y] + 1
	return -1
(x_init, y_init, x_fin, y_fin) = map(int, input().split())
n = int(input())
allowed = defaultdict(lambda : False)
for i in range(n):
	(r, a, b) = map(int, input().split())
	for j in range(a, b + 1):
		allowed[r, j] = True
print(bfs(x_init, y_init, x_fin, y_fin, allowed))


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])


from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from fractions import Fraction
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(sx, sy, ex, ey) = gil()
(d, h) = ({}, [])
for _ in range(gil()[0]):
	(r, L, R) = gil()
	for c in range(L, R + 1):
		d[r, c] = inf
if (sx, sy) not in d or (ex, ey) not in d:
	print(0 if (sx, sy) == (ex, ey) else -1)
	exit()
d[sx, sy] = 0
h.append((0, sx, sy))
perm = [(-1, -1), (1, 0), (0, 1), (1, 1), (0, -1), (-1, 0), (-1, 1), (1, -1)]
while h:
	(di, x, y) = heappop(h)
	if d[x, y] != di:
		continue
	for (dx, dy) in perm:
		p = (x + dx, y + dy)
		if p in d and d[p] > di + 1:
			d[p] = di + 1
			heappush(h, (di + 1, p[0], p[1]))
print(-1 if d[ex, ey] == inf else d[ex, ey])


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 sys import stdin

def main():
	(x, y, u, v) = map(int, input().split())
	input()
	rows = set()
	for st in stdin.read().splitlines():
		(r, a, b) = map(int, st.split())
		rows.update(((r, x) for x in range(a, b + 1)))
	(nxt, visited, cnt) = ([(x, y)], {(x, y)}, 0)
	while nxt:
		(cur, nxt) = (nxt, [])
		for (x, y) in cur:
			if x == u and y == v:
				print(cnt)
				return
			for xy in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1), (x - 1, y - 1), (x + 1, y - 1), (x - 1, y + 1), (x + 1, y + 1)):
				if xy in rows and xy not in visited:
					visited.add(xy)
					nxt.append(xy)
		cnt += 1
	print(-1)
main()


(x0, y0, x1, y1) = map(int, input().split())
n = int(input())
graph = set()
visited = set()
for i in range(n):
	(row, start, end) = map(int, input().split())
	for col in range(start, end + 1):
		graph.add((row, col))
dirs = ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1))
frontier = [(x0, y0)]
i = 0
while frontier:
	level = []
	for (x, y) in frontier:
		if (x, y) == (x1, y1):
			print(i)
			exit()
		for (dx, dy) in dirs:
			if (x + dx, y + dy) in graph and (x + dx, y + dy) not in visited:
				visited.add((x + dx, y + dy))
				level.append((x + dx, y + dy))
	frontier = level
	i += 1
print(-1)


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)
	exit()
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)
				exit()
			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)


(x, y, u, v) = map(int, input().split())
n = int(input())
rows = set()
for i in range(n):
	(r, a, b) = map(int, input().split())
	rows.update(((r, x) for x in range(a, b + 1)))
(nxt, visited, cnt) = ([(x, y)], {(x, y)}, 0)
flag = True
while nxt:
	(cur, nxt) = (nxt, [])
	for (x, y) in cur:
		if x == u and y == v:
			print(cnt)
			exit()
		for xy in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1), (x - 1, y - 1), (x + 1, y - 1), (x - 1, y + 1), (x + 1, y + 1)):
			if xy in rows and xy not in visited:
				visited.add(xy)
				nxt.append(xy)
	cnt += 1
print('-1')


from bisect import bisect_left
(x0, y0, x1, y1) = map(int, input().split())
n = int(input())
allowed = {}
for i in range(n):
	(r, a, b) = map(int, input().split())
	if r - 1 not in allowed:
		allowed[r - 1] = []
	allowed[r - 1].append([a - 1, b - 1])
for each in allowed:
	i = 0
	allowed[each].sort()
	while i < len(allowed[each]) - 1:
		if allowed[each][i][1] >= allowed[each][i + 1][0]:
			allowed[each][i][1] = max(allowed[each][i][1], allowed[each][i + 1][1])
			del allowed[each][i + 1]
		else:
			i += 1

def code(x, y):
	return x * 10 ** 9 + y
q = [[code(x0 - 1, y0 - 1), 0]]
v = {code(x0 - 1, y0 - 1)}
f = False
while q:
	node = q[0]
	(x, y) = (node[0] // 10 ** 9, node[0] % 10 ** 9)
	d = node[1]
	del q[0]
	if x == x1 - 1 and y == y1 - 1:
		f = True
		break
	c = code(x + 1, y)
	if c not in v and x < 10 ** 9 - 1 and (x + 1 in allowed):
		r = x + 1
		i = bisect_left(allowed[r], [y, y])
		n = len(allowed[r])
		if i != n and allowed[r][i][0] == y or (i > 0 and allowed[r][i - 1][1] >= y):
			q.append([c, d + 1])
			v.add(c)
	c = code(x - 1, y)
	if c not in v and x > 0 and (x - 1 in allowed):
		r = x - 1
		i = bisect_left(allowed[r], [y, y])
		n = len(allowed[r])
		if i != n and allowed[r][i][0] == y or (i > 0 and allowed[r][i - 1][1] >= y):
			q.append([c, d + 1])
			v.add(c)
	c = code(x, y + 1)
	if c not in v and y < 10 ** 9 - 1 and (x in allowed):
		r = x
		i = bisect_left(allowed[r], [y + 1, y + 1])
		n = len(allowed[r])
		if i != n and allowed[r][i][0] == y + 1 or (i > 0 and allowed[r][i - 1][1] >= y + 1):
			q.append([c, d + 1])
			v.add(c)
	c = code(x, y - 1)
	if c not in v and y > 0 and (x in allowed):
		r = x
		i = bisect_left(allowed[r], [y - 1, y - 1])
		n = len(allowed[r])
		if i != n and allowed[r][i][0] == y - 1 or (i > 0 and allowed[r][i - 1][1] >= y - 1):
			q.append([c, d + 1])
			v.add(c)
	c = code(x + 1, y + 1)
	if c not in v and y < 10 ** 9 - 1 and (x < 10 ** 9 - 1) and (x + 1 in allowed):
		r = x + 1
		i = bisect_left(allowed[r], [y + 1, y + 1])
		n = len(allowed[r])
		if i != n and allowed[r][i][0] == y + 1 or (i > 0 and allowed[r][i - 1][1] >= y + 1):
			q.append([c, d + 1])
			v.add(c)
	c = code(x + 1, y - 1)
	if c not in v and y > 0 and (x < 10 ** 9 - 1) and (x + 1 in allowed):
		r = x + 1
		i = bisect_left(allowed[r], [y - 1, y - 1])
		n = len(allowed[r])
		if i != n and allowed[r][i][0] == y - 1 or (i > 0 and allowed[r][i - 1][1] >= y - 1):
			q.append([c, d + 1])
			v.add(c)
	c = code(x - 1, y + 1)
	if c not in v and y < 10 ** 9 - 1 and (x > 0) and (x - 1 in allowed):
		r = x - 1
		i = bisect_left(allowed[r], [y + 1, y + 1])
		n = len(allowed[r])
		if i != n and allowed[r][i][0] == y + 1 or (i > 0 and allowed[r][i - 1][1] >= y + 1):
			q.append([c, d + 1])
			v.add(c)
	c = code(x - 1, y - 1)
	if c not in v and y > 0 and (x > 0) and (x - 1 in allowed):
		r = x - 1
		i = bisect_left(allowed[r], [y - 1, y - 1])
		n = len(allowed[r])
		if i != n and allowed[r][i][0] == y - 1 or (i > 0 and allowed[r][i - 1][1] >= y - 1):
			q.append([c, d + 1])
			v.add(c)
if f:
	print(node[1])
else:
	print(-1)


from collections import deque
(x0, y0, x1, y1) = map(int, input().split())
n = int(input())
bars = {}
for i in range(n):
	(r, a, b) = 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 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


def approved(coord):
	if coord[0] in allowed:
		for pair in allowed[coord[0]]:
			if pair[0] <= coord[1] <= pair[1]:
				return True
	return False

def neighbours(cur):
	candidates = {(cur[0] - 1, cur[1] - 1), (cur[0] - 1, cur[1]), (cur[0] - 1, cur[1] + 1), (cur[0], cur[1] - 1), (cur[0], cur[1] + 1), (cur[0] + 1, cur[1] - 1), (cur[0] + 1, cur[1]), (cur[0] + 1, cur[1] + 1)}
	return {i for i in candidates if approved(i)}
(x0, y0, x1, y1) = map(int, input().split())
n = int(input())
allowed = {}
for i in range(n):
	(r, a, b) = map(int, input().split())
	if r not in allowed:
		allowed[r] = [(a, b)]
	else:
		allowed[r].append((a, b))
queue = [(x0, y0)]
visited = {(x0, y0): 0}
steps = 0
while len(queue) > 0:
	cur = queue.pop(0)
	for nbor in neighbours(cur):
		if nbor not in visited:
			queue.append(nbor)
			visited[nbor] = visited[cur] + 1
if (x1, y1) in visited:
	print(visited[x1, y1])
else:
	print(-1)


from queue import Queue

def main(arr, start, end):
	points = set([])
	for i in range(len(arr)):
		(row, x, y) = arr[i]
		for j in range(x, y + 1):
			points.add((row, j))
	dist = {start: 0}
	q = Queue(maxsize=0)
	q.put(start)
	while q.qsize() != 0:
		(x1, y1) = q.get()
		d = dist[x1, y1]
		if (x1, y1) == end:
			return dist[end]
		for i in range(-1, 2):
			for j in range(-1, 2):
				p = (x1 + i, y1 + j)
				if p not in dist and p in points:
					dist[p] = 1 + d
					q.put(p)
	return -1
(a1, b1, a2, b2) = list(map(int, input().split()))
start = (a1, b1)
end = (a2, b2)
n = int(input())
arr = []
for i in range(n):
	arr.append(list(map(int, input().split())))
print(main(arr, start, end))


(x0, y0, x1, y1) = map(int, input().split())
m = dict()
for _ in range(int(input())):
	(r, a, b) = map(int, input().split())
	for i in range(a, b + 1):
		m[r, i] = -1
m[x0, y0] = 0
q = [(x0, y0)]
dx = [-1, 1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, 1, -1, -1, 1, 1, -1]
while len(q) > 0:
	k = q.pop(0)
	for i in range(8):
		(r, c) = (k[0] + dx[i], k[1] + dy[i])
		if (r, c) in m.keys() and m[r, c] == -1:
			q.append((r, c))
			m[r, c] = m[k[0], k[1]] + 1
print(m[x1, y1])


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):
	global limit
	val = x
	val = val * limit + y
	return val

def bfs():
	global 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) = 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) = map(int, input().split())
	for j in range(a, b + 1):
		mark.add(calc(r, j))
bfs()


def connect_point(graph, r, j, deg):
	if (r - 1, j) in graph and deg < graph[r - 1, j][0]:
		graph[r - 1, j][0] = deg
		graph[r, j].append((r - 1, j))
	if (r + 1, j) in graph and deg < graph[r + 1, j][0]:
		graph[r + 1, j][0] = deg
		graph[r, j].append((r + 1, j))
	if (r, j - 1) in graph and deg < graph[r, j - 1][0]:
		graph[r, j - 1][0] = deg
		graph[r, j].append((r, j - 1))
	if (r, j + 1) in graph and deg < graph[r, j + 1][0]:
		graph[r, j + 1][0] = deg
		graph[r, j].append((r, j + 1))
	if (r - 1, j - 1) in graph and deg < graph[r - 1, j - 1][0]:
		graph[r - 1, j - 1][0] = deg
		graph[r, j].append((r - 1, j - 1))
	if (r - 1, j + 1) in graph and deg < graph[r - 1, j + 1][0]:
		graph[r - 1, j + 1][0] = deg
		graph[r, j].append((r - 1, j + 1))
	if (r + 1, j - 1) in graph and deg < graph[r + 1, j - 1][0]:
		graph[r + 1, j - 1][0] = deg
		graph[r, j].append((r + 1, j - 1))
	if (r + 1, j + 1) in graph and deg < graph[r + 1, j + 1][0]:
		graph[r + 1, j + 1][0] = deg
		graph[r, j].append((r + 1, j + 1))

def bfs(graph):
	res = -1
	deg = 1
	queue = []
	queue.append((sr, sc, 0))
	while queue:
		item = queue.pop(0)
		if item[0] == fr and item[1] == fc:
			res = item[2]
			break
		connect_point(graph, item[0], item[1], item[2] + 1)
		for i in graph[item[0], item[1]]:
			if type(i) == int:
				continue
			queue.append((i[0], i[1], item[2] + 1))
		deg += 1
	return res
(sr, sc, fr, fc) = [int(i) for i in input().split()]
n = int(input())
graph = {}
graph[sr, sc] = [0]
graph[fr, fc] = [100000000000]
for i in range(n):
	(r, a, b) = [int(i) for i in input().split()]
	for j in range(a, b + 1):
		if (r, j) not in graph:
			graph[r, j] = [100000000000]
ret = bfs(graph)
print(ret)


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])


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, 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)


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])
		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
		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 check_path(xs, ys, xe, ye, dct, visited):
	xchange = [1, -1, 1, -1, 1, -1, 0, 0]
	ychange = [1, -1, -1, 1, 0, 0, 1, -1]
	i = 0
	if ye == ys and xe == xs:
		return 0
	node = [ys, xs, 0]
	visited.append(node)
	while len(visited):
		xs = visited[0][1]
		ys = visited[0][0]
		steps = visited[0][2] + 1
		for m in range(8):
			mx = xs + xchange[m]
			my = ys + ychange[m]
			node = [my, mx, steps]
			if my == ye and mx == xe:
				return steps
			if (my, mx) in dct:
				visited.append(node)
				del dct[my, mx]
		visited.pop(0)
		i += 1
	return -1
dct = {}
visited = []
(y1, x1, y2, x2) = [int(i) for i in input().split()]
n = int(input())
for _ in range(n):
	(r, a, b) = [int(i) for i in input().split()]
	for i in range(a, b + 1):
		s = str([r, i])
		dct[r, i] = 1
print(check_path(x1, y1, x2, y2, dct, visited))


from collections import deque
(x, y, x2, y2) = map(int, input().split())
n = int(input())
kletki = {}
for i in range(n):
	(r, a, b) = map(int, input().split())
	for j in range(a, b + 1):
		kletki[r, j] = -1
kletki[x, y] = 0
deq = deque()
deq.append((x, y))
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
while len(deq):
	m = deq.popleft()
	for k in range(8):
		n = (m[0] + dx[k], m[1] + dy[k])
		if n in kletki.keys():
			if m in kletki and kletki[n] == -1:
				kletki[n] = kletki[m] + 1
				deq.append(n)
print(kletki[x2, y2])


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
(x0, y0, x1, y1) = map(int, input().split(' '))
start = (x0, y0, 0)
end = (x1, y1)
n = int(input())
valid = set()
for i in range(n):
	(row, l, h) = map(int, input().split())
	for i in range(l, h + 1, 1):
		valid.add((row, i))
dx = [0, 0, 1, -1, 1, 1, -1, -1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
q = [start]
visited = set()
visited.add((start[0], start[1]))
while len(q) > 0:
	current = q[0]
	q.pop(0)
	if current[0] == end[0] and current[1] == end[1]:
		print(current[2])
		exit(0)
	for i in range(0, 8, 1):
		if (current[0] + dx[i], current[1] + dy[i]) in valid and (current[0] + dx[i], current[1] + dy[i]) not in visited:
			q.append((current[0] + dx[i], current[1] + dy[i], current[2] + 1))
			visited.add((current[0] + dx[i], current[1] + dy[i]))
print(-1)


INF = 1000000000

def bfs(sta, fin):
	from collections import deque
	visit = deque()
	dx = [0, -1, -1, -1, 0, 1, 1, 1]
	dy = [1, 1, 0, -1, -1, -1, 0, 1]
	visit.append(sta)
	while len(visit) > 0:
		vertex = visit.popleft()
		for i in range(8):
			nx = vertex[0] + dx[i]
			ny = vertex[1] + dy[i]
			if 1 <= nx <= INF and 1 <= ny <= INF and ((nx, ny) in board) and (board[nx, ny] == -1):
				visit.append((nx, ny))
				board[nx, ny] = 0
				dist[nx, ny] = dist[vertex] + 1
				if (nx, ny) == fin:
					print(dist[nx, ny], end='')
					return True
	return False
(board, dist) = (dict(), dict())
(x0, y0, x1, y1) = map(int, input().split())
sta = (x0, y0)
fin = (x1, y1)
dist[sta] = 0
n = int(input())
for _ in range(n):
	line = input()
	(r, a, b) = map(int, line.split())
	for i in range(a, b + 1):
		board[r, i] = -1
		dist[r, i] = 0
if not bfs(sta, fin):
	print(-1, end='')


from collections import deque, defaultdict
import itertools
(x, y, xf, yf) = map(int, input().split())
n = int(input())
allowed_cell = set()
for _ in range(n):
	(r, a, b) = map(int, input().split())
	for cell in range(a, b + 1):
		allowed_cell.add((r, cell))
dst = defaultdict(lambda : -1)
dst[x, y] = 0
q = deque()
q.append((x, y))
while len(q):
	(i, j) = q.popleft()
	for d in itertools.product((0, 1, -1), repeat=2):
		ni = i + d[0]
		nj = j + d[1]
		if 0 < ni <= 10 ** 9 and 0 < nj <= 10 ** 9 and ((ni, nj) in allowed_cell) and (dst[ni, nj] == -1):
			dst[ni, nj] = dst[i, j] + 1
			q.append((ni, nj))
			if (ni, nj) == (xf, yf):
				break
print(dst[xf, yf])


def successors(pos):
	(x, y) = pos
	nextMoves = []
	if (x - 1, y) in allowed:
		nextMoves.append((x - 1, y))
	if (x + 1, y) in allowed:
		nextMoves.append((x + 1, y))
	if (x, y - 1) in allowed:
		nextMoves.append((x, y - 1))
	if (x, y + 1) in allowed:
		nextMoves.append((x, y + 1))
	if (x - 1, y - 1) in allowed:
		nextMoves.append((x - 1, y - 1))
	if (x - 1, y + 1) in allowed:
		nextMoves.append((x - 1, y + 1))
	if (x + 1, y - 1) in allowed:
		nextMoves.append((x + 1, y - 1))
	if (x + 1, y + 1) in allowed:
		nextMoves.append((x + 1, y + 1))
	return nextMoves

def BFS(start, end):
	explored = {}
	if start == end:
		return 0
	frontier = [start]
	explored[start] = 1
	h = 1
	while frontier:
		nextLevel = []
		for curPos in frontier:
			for (x, y) in successors(curPos):
				if (x, y) not in explored:
					explored[x, y] = 1
					if (x, y) == end:
						return h
					nextLevel.append((x, y))
		frontier = nextLevel
		h += 1
	return -1
allowed = {}
inp = str(input()).split(' ')
x0 = int(inp[0])
y0 = int(inp[1])
x1 = int(inp[2])
y1 = int(inp[3])
segs = int(input())
for _ in range(segs):
	inp = [int(i) for i in str(input()).split(' ')]
	for x in range(inp[1], inp[2] + 1):
		allowed[inp[0], x] = 1
print(BFS((x0, y0), (x1, y1)))


import sys
from collections import deque
input = sys.stdin.readline
(sx, sy, gx, gy) = map(int, input().split())
n = int(input())
rab = [list(map(int, input().split())) for i in range(n)]
good = set()
vis = {}
for (r, a, b) in rab:
	for c in range(a, b + 1):
		good.add((r, c))
dq = deque()
dq.append([sx, sy, 0])
vis[sx, sy] = 0
while dq:
	(x, y, c) = dq.popleft()
	for dx in [-1, 0, 1]:
		for dy in [-1, 0, 1]:
			if dx == dy == 0:
				continue
			pos = (x + dx, y + dy)
			if pos in good and (not pos in vis):
				vis[pos] = c + 1
				dq.append([x + dx, y + dy, c + 1])
if (gx, gy) in vis:
	print(vis[gx, gy])
else:
	print(-1)


from collections import deque

def bfs(x0, y0, x1, y1, dic):
	visited = {}
	x = [1, -1, 0, 0, -1, -1, 1, 1]
	y = [0, 0, -1, 1, 1, -1, 1, -1]
	q = deque()
	q.append((x0, y0, 0))
	visited[x0, y0] = 1
	while q != deque([]):
		a = q.popleft()
		for i in range(8):
			if (a[0] + x[i], a[1] + y[i]) in dic and (a[0] + x[i], a[1] + y[i]) not in visited:
				visited[a[0] + x[i], a[1] + y[i]] = 1
				q.append((a[0] + x[i], a[1] + y[i], a[2] + 1))
				if (a[0] + x[i], a[1] + y[i]) == (x1, y1):
					return [True, a[2] + 1]
	return [False]
(x0, y0, x1, y1) = map(int, input().split())
n = int(input())
dic = {}
for i in range(n):
	arr = [int(i) for i in input().split()]
	i = arr[0]
	for j in range(arr[1], arr[2] + 1):
		if (i, j) not in dic:
			dic[i, j] = 1
res = bfs(x0, y0, x1, y1, dic)
if res[0]:
	print(res[1])
else:
	print(-1)


import sys, os.path
from collections import *
from heapq import *
from copy import *
import math
mod = 10 ** 9 + 7
read = lambda : map(int, input().split())
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
l1 = [0, 0, 1, 1, 1, -1, -1, -1]
l2 = [1, -1, -1, 0, 1, -1, 0, 1]
(x1, y1, x2, y2) = read()
n = int(input())
path = defaultdict(int)
for i in range(n):
	(r, a, b) = read()
	for j in range(a, b + 1):
		path[r, j] = 1
vis = defaultdict(int)
q = deque()
q.append((x1, y1))
vis[x1, x2] = 1
dis = defaultdict(int)
dis[x1, y1] = 0
flag = 0
while len(q):
	(x, y) = q.popleft()
	for k in range(8):
		(p1, p2) = (x + l1[k], y + l2[k])
		if not vis[p1, p2] and path[p1, p2] == 1:
			q.append((p1, p2))
			dis[p1, p2] = dis[x, y] + 1
			vis[p1, p2] = 1
			if (p1, p2) == (x2, y2):
				flag = 1
				break
	if flag == 1:
		break
ans = dis[x2, y2]
if ans == 0:
	print(-1)
else:
	print(ans)


from collections import deque

def neighs(x0, x1):
	return [(x0, x1 + 1), (x0 + 1, x1 + 1), (x0 + 1, x1), (x0 + 1, x1 - 1), (x0, x1 - 1), (x0 - 1, x1 - 1), (x0 - 1, x1), (x0 - 1, x1 + 1)]

def bfs(x0, x1, y0, y1, allowed):
	fifo = deque([(x0, x1, 0)])
	while fifo:
		(x0, x1, d) = fifo.pop()
		for (n0, n1) in neighs(x0, x1):
			if (n0, n1) in allowed:
				allowed.remove((n0, n1))
				fifo.appendleft((n0, n1, d + 1))
		if (x0, x1) == (y0, y1):
			return d
	return -1

def solve():
	(x0, x1, y0, y1) = map(int, input().split())
	n = int(input())
	allowed = set()
	for _ in range(n):
		(r, a, b) = map(int, input().split())
		for c in range(a, b + 1):
			allowed.add((r, c))
	val = bfs(x0, x1, y0, y1, allowed)
	print(val)
solve()


from sys import stdin
from collections import *
(dx, dy) = ([-1, 0, 1, 0, 1, -1, 1, -1], [0, 1, 0, -1, 1, -1, -1, 1])

def arr_inp(n):
	return [int(x) for x in stdin.readline().split()]

def valid(x, y):
	return True if x >= 0 and x <= 1000000000 and (y >= 0) and (y <= 1000000000) and mem[x, y] else False

def bfs_util():
	(queue, visit, ans) = (deque([[x0, y0, 0]]), defaultdict(int), float('inf'))
	while queue:
		(x, y, move) = queue.popleft()
		if x == x1 and y == y1:
			ans = min(ans, move)
			break
		for i in range(8):
			(nx, ny) = (x + dx[i], y + dy[i])
			if valid(nx, ny) and (not visit[nx, ny]):
				queue.append([nx, ny, move + 1])
				visit[nx, ny] = 1
	return ans if ans != float('inf') else -1
(x0, y0, x1, y1) = arr_inp(1)
(mem, n) = (defaultdict(int), int(input()))
for i in range(n):
	(r, a, b) = arr_inp(1)
	for j in range(a, b + 1):
		mem[r, j] = 1
print(bfs_util())


from sys import stdin, stdout
from collections import deque
(x0, y0, x1, y1) = map(int, stdin.readline().split())
n = int(stdin.readline())
allowed = {}
for _ in range(n):
	(r, a, b) = map(int, stdin.readline().split())
	if r in allowed:
		allowed[r].append([a, b])
	else:
		allowed[r] = [[a, b]]
for r in allowed:
	old = allowed[r]
	old.sort(key=lambda x: x[0])
	compressed = [old[0]]
	for i in range(1, len(old)):
		if old[i][0] <= compressed[-1][1]:
			compressed[-1][1] = max(old[i][1], compressed[-1][1])
		else:
			compressed.append(old[i])
	allowed[r] = compressed

def check_valid(r, box):
	if r <= 0 or box <= 0 or r > 1000000000.0 or (box > 1000000000.0):
		return False
	if r not in allowed:
		return False
	for (a, b) in allowed[r]:
		if a <= box <= b:
			return True
	return False

def bfs(start, target):
	q = deque()
	q.append((start, 0))
	visited = set()
	while q:
		(square, moves) = q.popleft()
		dr = [-1, -1, 0, 1, 1, 1, 0, -1]
		dx = [0, 1, 1, 1, 0, -1, -1, -1]
		for i in range(8):
			new_square = (square[0] + dr[i], square[1] + dx[i])
			if check_valid(*new_square) and new_square not in visited:
				if new_square == target:
					return moves + 1
				q.append((new_square, moves + 1))
				visited.add(new_square)
	return -1
print(bfs((x0, y0), (x1, y1)))


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def isBetween(x, l, h):
	if x >= l and x <= h:
		return True
	else:
		return False

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
cord = [(0, 1), (0, -1), (-1, 0), (1, 0), (1, 1), (-1, -1), (-1, 1), (1, -1)]

def bfs(s, d):
	vis = defaultdict(bool)
	vis[s] = True
	qu = [s]
	dis = defaultdict(lambda : inf)
	dis[s] = 0
	while len(qu) != 0:
		ele = qu.pop(0)
		if ele == d:
			return dis[ele]
		for i in cord:
			x = ele[0] + i[0]
			y = ele[1] + i[1]
			if not vis[x, y] and safe[x, y]:
				qu.append((x, y))
				dis[x, y] = min(dis[ele] + 1, dis[x, y])
				vis[x, y] = True
	return -1
(x1, y1, x2, y2) = value()
safe = defaultdict(bool)
for i in range(Int()):
	(r, i, j) = value()
	for co in range(i, j + 1):
		safe[r, co] = True
print(bfs((x1, y1), (x2, y2)))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(x1, y1, x2, y2) = map(int, input().split())
from collections import defaultdict, deque
adj = defaultdict(list)
n = int(input())
d = defaultdict(int)
l1 = [0, 0, 1, 1, 1, -1, -1, -1]
l2 = [1, -1, -1, 0, 1, -1, 0, 1]
for i in range(n):
	(r, a, b) = map(int, input().split())
	for j in range(a, b + 1):
		d[r, j] = 1
v = defaultdict(int)
q = deque([])
q.append((x1, y1))
v[x1, y1] = 1
dis = defaultdict(int)
dis[x1, y1] = 0
a = False
while len(q):
	(x, y) = q.popleft()
	for i in range(8):
		(p1, p2) = (x + l1[i], y + l2[i])
		if not v[p1, p2] and d[p1, p2] == 1:
			q.append((p1, p2))
			dis[p1, p2] = dis[x, y] + 1
			v[p1, p2] = 1
			if (p1, p2) == (x2, y2):
				a = True
				break
	if a:
		break
ans = dis[x2, y2]
if ans == 0:
	print(-1)
else:
	print(ans)


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
	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))


from collections import deque as Q
(x0, y0, x1, y1) = [int(i) for i in input().split(' ')]
n = int(input())
graph = {}
nX = [-1, 0, 1, -1, 1, -1, 0, 1]
nY = [-1, -1, -1, 0, 0, 1, 1, 1]
for i in range(n):
	(r, a, b) = [int(i) for i in input().split(' ')]
	for j in range(a, b + 1):
		graph[r, j] = -1
graph[x0, y0] = 0
q = Q([(x0, y0)])
while q:
	c = q.popleft()
	for i in range(8):
		neighbour = (c[0] + nX[i], c[1] + nY[i])
		if neighbour in graph and graph[neighbour] == -1:
			q.append(neighbour)
			graph[neighbour] = graph[c] + 1
print(graph[x1, y1])


from collections import deque
import sys
input = sys.stdin.readline

def bfs(x, y, x2, y2, moves, seg):
	q = deque([])
	q.append((x, y, moves))
	rw = [0, 0, -1, 1, -1, -1, 1, 1]
	cl = [1, -1, 0, 0, -1, 1, -1, 1]
	visited = dict()
	visited[x, y] = 1
	while q:
		curr = q.popleft()
		if curr[0] == x2 and curr[1] == y2:
			return curr[2]
		for w in range(8):
			if (curr[0] + rw[w], curr[1] + cl[w]) not in visited:
				if (curr[0] + rw[w], curr[1] + cl[w]) in seg:
					q.append((curr[0] + rw[w], curr[1] + cl[w], curr[2] + 1))
					visited[curr[0] + rw[w], curr[1] + cl[w]] = 1
	return -1
(x, y, x2, y2) = [int(x) for x in input().split()]
n = int(input())
seg = set()
for i in range(n):
	(r, a, b) = [int(t) for t in input().split()]
	for q in range(a, b + 1):
		seg.add((r, q))
print(bfs(x, y, x2, y2, 0, seg))


MAX = 10 ** 9
d_row = [-1, -1, -1, 0, 0, 1, 1, 1]
d_clm = [-1, 0, 1, -1, 1, -1, 0, 1]

def BFS(S, T):
	dist[S] = 0
	queue = [S]
	while queue:
		u = queue.pop(0)
		if u == T:
			break
		u_row = u // MAX
		u_clm = u % MAX
		for i in range(8):
			v = (u_row + d_row[i]) * MAX + u_clm + d_clm[i]
			if v in dist and dist[v] == MAX:
				queue.append(v)
				dist[v] = dist[u] + 1
	return -1 if dist[T] == MAX else dist[T]
dist = {}
(s_row, s_clm, t_row, t_clm) = map(int, input().split())
S = s_row * MAX + s_clm
dist[S] = MAX
T = t_row * MAX + t_clm
dist[T] = MAX
n = int(input())
for _ in range(n):
	(r, a, b) = map(int, input().split())
	for i in range(a, b + 1):
		dist[r * MAX + i] = MAX
print(BFS(S, T))


import collections

def kingpath():

	def adds(x, y, c):
		s = (x, y)
		if s in sgs and s not in his:
			todo.append([x, y, c + 1])
			his.add(s)
	(startx, starty, endx, endy) = map(int, input().split())
	seg = int(input())
	sgs = set()
	for i in range(seg):
		(row, s, e) = map(int, input().split())
		for i1 in range(s, e + 1):
			sgs.add((row, i1))
	todo = collections.deque([[startx, starty, 0]])
	his = set()
	while todo:
		(x, y, step) = todo.popleft()
		if x == endx and y == endy:
			return step
		adds(x - 1, y, step)
		adds(x + 1, y, step)
		adds(x, y - 1, step)
		adds(x, y + 1, step)
		adds(x - 1, y - 1, step)
		adds(x + 1, y + 1, step)
		adds(x - 1, y + 1, step)
		adds(x + 1, y - 1, step)
	return -1
print(kingpath())


(x0, y0, x1, y1) = map(int, input().split())
n = int(input())
g = set()
for _ in range(n):
	(a, b, c) = map(int, input().split())
	for i in range(b, c + 1):
		g.add((a, i))
moves = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, -1), (1, 1), (-1, -1), (-1, 1)]
q = [(x0, y0, 0)]
g.remove((x0, y0))
ans = -1
while q:
	temp = q.pop(0)
	if temp[:2] == (x1, y1):
		ans = max(ans, temp[2])
	for move in moves:
		temp_move = (temp[0] + move[0], temp[1] + move[1], temp[2] + 1)
		if len(g) == 0 or not temp_move[:2] in g:
			continue
		q += [temp_move]
		g.remove(temp_move[:2])
print(ans)


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()


(x0, y0, x1, y1) = map(int, input().split())
n = int(input())
rows = set()
for _ in range(n):
	(r, a, b) = map(int, input().split())
	rows.update(((r, x) for x in range(a, b + 1)))
(neighbors, visited, moves) = ([(x0, y0)], {x0, y0}, 0)
while neighbors:
	(current, neighbors) = (neighbors, [])
	for (x, y) in current:
		if (x, y) == (x1, y1):
			print(moves)
			exit()
		for xy in ((x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1), (x + 1, y + 1), (x - 1, y - 1), (x + 1, y - 1), (x - 1, y + 1)):
			if xy in rows and xy not in visited:
				visited.add(xy)
				neighbors.append(xy)
	moves += 1
print(-1)


from collections import deque
import sys
input = sys.stdin.readline
xadj = [0, 0, -1, 1, -1, -1, 1, 1]
yadj = [1, -1, 0, 0, -1, 1, -1, 1]
(res, vis) = (set(), dict())
(x0, y0, x1, y1) = map(int, input().split())
n = int(input())
for seg in range(n):
	(r, a, b) = map(int, input().split())
	for c in range(a, b + 1):
		res.add((r, c))
pnts = deque()
pnts.append((x0, y0, 0))
vis[x0, y0] = 0
while len(pnts) > 0:
	cur = pnts.popleft()
	for i in range(8):
		pos = (cur[0] + xadj[i], cur[1] + yadj[i])
		if pos in res and pos not in vis:
			pnts.append((pos[0], pos[1], cur[2] + 1))
			vis[pos] = cur[2] + 1
print(vis[x1, y1] if (x1, y1) in vis else -1)