from collections import deque, defaultdict, Counter from bisect import bisect_left, bisect_right, insort from itertools import permutations, combinations, groupby from heapq import heappop, heappush import math, sys input = lambda: sys.stdin.readline().rstrip("\r\n") def printl(li, sep=" "): print(sep.join(map(str, li))) def yn(flag): print(Yes if flag else No) _int = lambda x: int(x)-1 MOD = 998244353 #10**9+7 INF = 1<<60 Yes, No = "Yes", "No" import heapq import collections MEMORY_CAP: int = 130000 class Graph: shift: int mask: int _n: int _E: list[list[int]] _max_cost: int _dist: list[int] _vis: list[int] _bf: list[int] _last_start: int def __init__(self, n: int): self.shift = (n-1).bit_length() self.mask = (1< None: self._dist = [INF]*self._n self._vis = [0]*self._n self._bf = [-1]*self._n def add_edge(self, u: int, v: int, c: int = 1) -> None: assert 0 <= u < self._n assert 0 <= v < self._n assert 0 <= c if self._max_cost < c: self._max_cost = c self._E[u].append(c< None: border = MEMORY_CAP//self._n if self._max_cost <= 1: self.bfs01(start) elif self._max_cost <= border: self.dials_algorithm(start) else: self.dijkstra(start) def dijkstra(self, start: int) -> None: assert 0 <= start < self._n self._init_data() self._dist[start] = 0 self._last_start = start q = [start] while q: ni = heapq.heappop(q) cost, i = ni >> self.shift, ni & self.mask if self._vis[i]: continue self._vis[i] = 1 for nj in self._E[i]: c, j = nj >> self.shift, nj & self.mask tc = cost+c if self._vis[j]: continue if self._dist[j] <= tc: continue self._dist[j] = tc self._bf[j] = i heapq.heappush(q, tc< None: assert 0 <= start < self._n self._init_data() _m = self._n*self._max_cost B = [-1]*(_m + 1) # first L = [-1]*(_m + 1) # last *prv, = range(-1, self._n-1) *nxt, = range(1, self._n+1) nxt[-1] = -1 if start < self._n-1: prv[start+1] = (start-1 if start > 0 else -1) if start > 0: nxt[start-1] = (start+1 if start < self._n-1 else -1) prv[start] = nxt[start] = -1 B[0] = L[0] = start B[_m] = (1 if start == 0 else 0) L[_m] = (self._n-1 if start < self._n-1 else self._n-2) self._dist[start] = 0 self._last_start = start for w in range(_m): i = B[w] while i != -1: self._vis[i] = 1 for nj in self._E[i]: c, j = nj >> self.shift, nj & self.mask tc = w + c if tc >= self._dist[j]: continue d = self._dist[j] if d > _m: d = _m self._dist[j] = tc p = prv[j] n = nxt[j] if p != -1: nxt[p] = n else: B[d] = n if n != -1: prv[n] = p else: L[d] = p l = L[tc] if l != -1: nxt[l] = j else: B[tc] = j prv[j] = l nxt[j] = -1 self._bf[j] = i L[tc] = j i = nxt[i] def bfs01(self, start: int) -> None: assert 0 <= start < self._n self._init_data() self._dist[start] = 0 self._last_start = start q = collections.deque[int]([start]) while q: i = q.popleft() if self._vis[i]: continue self._vis[i] = 1 for nj in self._E[i]: c, j = nj >> self.shift, nj & self.mask assert 0 <= c <= 1 tc = self._dist[i]+c if self._vis[j]: continue if self._dist[j] <= tc: continue self._dist[j] = tc self._bf[j] = i if c == 0: q.appendleft(j) else: q.append(j) def dist(self, goal: int) -> int: return self._dist[goal] def vis(self, goal: int) -> int: return self._vis[goal] def path_to(self, goal: int) -> list[int]: assert 0 <= goal < self._n if self._vis[goal] == 0: return [] cur = goal ret = [cur] while cur != self._last_start: cur = self._bf[cur] ret.append(cur) ret.reverse() return ret H, W = map(int, input().split()) si, sj = map(_int, input().split()) A, B, C, D = map(_int, input().split()) ti, tj = map(_int, input().split()) G = Graph(H*W) dir = [(0, 1), (1, 0), (0, -1), (-1, 0)] for i in range(H): for j in range(W): for d in dir: ni, nj = i+d[0], j+d[1] if not(0 <= ni < H and 0 <= nj < W): continue G.add_edge(i*W+j, ni*W+nj) G.calc_dist(si*W+sj) memo = [0]*H*W cost = G.dist(ti*W+tj) for i in range(A, C+1): for j in range(B, D+1): memo[i*W+j] = G.dist(i*W+j) G.calc_dist(ti*W+tj) ans = INF for i in range(A, C+1): for j in range(B, D+1): ans = min(ans, memo[i*W+j]+G.dist(i*W+j)+cost) print(ans)