Problem: A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is `#` and a road if S_{ij} is `.`.

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

* Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.
* Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.



In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

* 1 \leq H,W \leq 10^3
* 1 \leq C_h,D_h \leq H
* 1 \leq C_w,D_w \leq W
* S_{ij} is `#` or `.`.
* S_{C_h C_w} and S_{D_h D_w} are `.`.
* (C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:


H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}


Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print `-1` instead.

Examples

Input

4 4
1 1
4 4
..#.
..#.
.#..
.#..


Output

1


Input

4 4
1 4
4 1
.##.


.##.


Output

-1


Input

4 4
2 2
3 3
....
....
....
....


Output

0


Input

4 5
1 2
2 5
.###
.
..##
..##


Output

2

Solution (in JAVA):

Solution:
// package beginner00176;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.InputMismatchException;

public class Main {
	private static PrintWriter out;

	static int[][] d4 = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

	public static void solve() {
		In in = new In();
		// BEFORE SUBMISSION :: Change class name to Main and comment out package name
		// !!!
		int n = in.ni();
		int m = in.ni();
		int r1 = in.ni() - 1;
		int c1 = in.ni() - 1;
		int r2 = in.ni() - 1;
		int c2 = in.ni() - 1;
		char[][] grid = new char[n][m];
		for (int i = 0; i < n; i++)
			grid[i] = in.ns().toCharArray();

		int[] dsu = new int[n * m];
		Arrays.fill(dsu, Integer.MAX_VALUE / 2);
		dsu[flatten(r1, c1, m)] = 0;
		Deque<int[]> q = new ArrayDeque<>();
		q.add(new int[] { r1, c1 });
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int r = cur[0];
			int c = cur[1];
			int src = flatten(r, c, m);
			for (int[] d : d4) {
				int nr = r + d[0];
				int nc = c + d[1];
				if (nr < 0 || nc < 0 || nr >= n || nc >= m || grid[nr][nc] == '#')
					continue;
				int dest = flatten(nr, nc, m);
				if (dsu[dest] > dsu[src]) {
					dsu[dest] = dsu[src];
					q.addFirst(new int[] { nr, nc });
				}
			}

			for (int nr = r - 2; nr <= r + 2; nr++) {
				for (int nc = c - 2; nc <= c + 2; nc++) {
					if (nr < 0 || nc < 0 || nr >= n || nc >= m || grid[nr][nc] == '#')
						continue;
					int dest = flatten(nr, nc, m);
					if (dsu[dest] > dsu[src] + 1) {
						dsu[dest] = dsu[src] + 1;
						q.addLast(new int[] { nr, nc });
					}
				}
			}
		}

		int dest = flatten(r2, c2, m);
		int ans = dsu[dest] >= Integer.MAX_VALUE / 2 ? -1 : dsu[dest];
		out.println(ans);

	}

	static int flatten(int r, int c, int C) {
		return r * C + c;
	}

	public static void main(String[] args) throws IOException {
		// long start = System.nanoTime();
		out = new PrintWriter(System.out);
		solve();
		out.flush();
		// System.out.println("Elapsed: " + (System.nanoTime() - start) / 1000000 +
		// "ns");
	}

	@SuppressWarnings("unused")
	private static class In {
		final private static int BUFFER_SIZE = 1024;
		private byte[] buf;
		private InputStream is;
		private int buflen;
		private int bufptr;

		public In() {
			is = System.in;
			buf = new byte[BUFFER_SIZE];
			buflen = bufptr = 0;
		}

		public In(String input) {
			is = new ByteArrayInputStream(input.getBytes());
			buf = new byte[BUFFER_SIZE];
			buflen = bufptr = 0;
		}

		public int readByte() {
			if (bufptr >= buflen) {
				try {
					buflen = is.read(buf);
				} catch (IOException ioe) {
					throw new InputMismatchException();
				}
				bufptr = 0;
			}
			if (buflen <= 0)
				return -1;
			return buf[bufptr++];
		}

		public boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}

		public int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b))
				;
			return b;
		}

		/* Next character */
		public char nc() {
			return (char) skip();
		}

		/* Next double */
		public double nd() {
			return Double.parseDouble(ns());
		}

		/* Next string */
		public String ns() {
			final StringBuilder sb = new StringBuilder();
			int b = skip();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		/* Next integer */
		public int ni() {
			boolean minus = false;
			int num = 0;
			int b;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			while (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
				b = readByte();
			}
			return minus ? -num : num;
		}

		/* Next long */
		public long nl() {
			boolean minus = false;
			long num = 0;
			int b;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			while (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
				b = readByte();
			}
			return minus ? -num : num;
		}

		/* Next integer 1D array */
		public int[] nia(int n) {
			final int[] arr = new int[n];
			for (int i = 0; i < n; i++)
				arr[i] = ni();
			return arr;
		}

		/* Next long 1D array */
		public long[] nla(int n) {
			final long[] arr = new long[n];
			for (int i = 0; i < n; i++)
				arr[i] = nl();
			return arr;
		}

		/* Next string 1D array */
		public String[] nsa(int n) {
			final String[] arr = new String[n];
			for (int i = 0; i < n; i++)
				arr[i] = ns();
			return arr;
		}

		/* Next char 1D array */
		public char[] nca(int n) {
			final char[] arr = new char[n];
			for (int i = 0; i < n; i++)
				arr[i] = nc();
			return arr;
		}

		/* Next double 1D array */
		public double[] nda(int n) {
			final double[] arr = new double[n];
			for (int i = 0; i < n; i++)
				arr[i] = nc();
			return arr;
		}

		/* Next integer matrix */
		public int[][] nim(int n, int m) {
			final int[][] arr = new int[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = ni();
			return arr;
		}

		/* Next long matrix */
		public long[][] nlm(int n, int m) {
			final long[][] arr = new long[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = nl();
			return arr;
		}

		/* Next string matrix */
		public String[][] nsm(int n, int m) {
			final String[][] arr = new String[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = ns();
			return arr;
		}

		/* Next char matrix */
		public char[][] ncm(int n, int m) {
			final char[][] arr = new char[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = nc();
			return arr;
		}

		/* Next double matrix */
		public double[][] ndm(int n, int m) {
			final double[][] arr = new double[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = nd();
			return arr;
		}

		public static void log(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
	}

}