{"raw_statement":[{"iden":"problem statement","content":"We have an $N \\times N$ chessboard. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left of this board.  \nThe board is described by $N$ strings $S_i$.  \nThe $j$\\-th character of the string $S_i$, $S_{i,j}$, means the following.\n\n*   If $S_{i,j}=$ `.`, the square $(i, j)$ is empty.\n*   If $S_{i,j}=$ `#`, the square $(i, j)$ is occupied by a white pawn, which cannot be moved or removed.\n\nWe have put a white bishop on the square $(A_x, A_y)$.  \nFind the minimum number of moves needed to move this bishop from $(A_x, A_y)$ to $(B_x, B_y)$ according to the rules of chess (see Notes).  \nIf it cannot be moved to $(B_x, B_y)$, report `-1` instead."},{"iden":"notes","content":"A white [bishop](https://en.wikipedia.org/wiki/Bishop_(chess)) on the square $(i, j)$ can go to the following positions in one move.\n\n*   For each positive integer $d$, it can go to $(i+d,j+d)$ if all of the conditions are satisfied.\n    *   The square $(i+d,j+d)$ exists in the board.\n    *   For every positive integer $l \\le d$, $(i+l,j+l)$ is not occupied by a white pawn.\n*   For each positive integer $d$, it can go to $(i+d,j-d)$ if all of the conditions are satisfied.\n    *   The square $(i+d,j-d)$ exists in the board.\n    *   For every positive integer $l \\le d$, $(i+l,j-l)$ is not occupied by a white pawn.\n*   For each positive integer $d$, it can go to $(i-d,j+d)$ if all of the conditions are satisfied.\n    *   The square $(i-d,j+d)$ exists in the board.\n    *   For every positive integer $l \\le d$, $(i-l,j+l)$ is not occupied by a white pawn.\n*   For each positive integer $d$, it can go to $(i-d,j-d)$ if all of the conditions are satisfied.\n    *   The square $(i-d,j-d)$ exists in the board.\n    *   For every positive integer $l \\le d$, $(i-l,j-l)$ is not occupied by a white pawn."},{"iden":"constraints","content":"*   $2 \\le N \\le 1500$\n*   $1 \\le A_x,A_y \\le N$\n*   $1 \\le B_x,B_y \\le N$\n*   $(A_x,A_y) \\neq (B_x,B_y)$\n*   $S_i$ is a string of length $N$ consisting of `.` and `#`.\n*   $S_{A_x,A_y}=$ `.`\n*   $S_{B_x,B_y}=$ `.`"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_x$ $A_y$\n$B_x$ $B_y$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$"},{"iden":"sample input 1","content":"5\n1 3\n3 5\n....#\n...#.\n.....\n.#...\n#...."},{"iden":"sample output 1","content":"3\n\nWe can move the bishop from $(1,3)$ to $(3,5)$ in three moves as follows, but not in two or fewer moves.\n\n*   $(1,3) \\rightarrow (2,2) \\rightarrow (4,4) \\rightarrow (3,5)$"},{"iden":"sample input 2","content":"4\n3 2\n4 2\n....\n....\n....\n...."},{"iden":"sample output 2","content":"\\-1\n\nThere is no way to move the bishop from $(3,2)$ to $(4,2)$."},{"iden":"sample input 3","content":"18\n18 1\n1 18\n..................\n.####.............\n.#..#..####.......\n.####..#..#..####.\n.#..#..###...#....\n.#..#..#..#..#....\n.......####..#....\n.............####.\n..................\n..................\n.####.............\n....#..#..#.......\n.####..#..#..####.\n.#.....####..#....\n.####.....#..####.\n..........#..#..#.\n.............####.\n.................."},{"iden":"sample output 3","content":"9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}