{"raw_statement":[{"iden":"problem statement","content":"There is a town represented as a two-dimensional grid with $H$ horizontal rows and $W$ vertical columns.  \nA character $a_{i,j}$ describes the square at the $i$\\-th row from the top and $j$\\-th column from the left. Here, $a_{i,j}$ is one of the following: `S` , `G` , `.` , `#` , `a`, ..., and `z`.  \n`#` represents a square that cannot be entered, and `a`, ..., `z` represent squares with teleporters.\nTakahashi is initially at the square represented as `S`. In each second, he will make one of the following moves:\n\n*   Go to a non-`#` square that is horizontally or vertically adjacent to his current position.\n*   Choose a square with the same character as that of his current position, and teleport to that square. He can only use this move when he is at a square represented as `a`, ..., or `z`.\n\nFind the shortest time Takahashi needs to reach the square represented as `G` from the one represented as `S`.  \nIf the destination is unreachable, report `-1` instead."},{"iden":"constraints","content":"*   $1 \\le H, W \\le 2000$\n*   $a_{i,j}$ is `S`, `G`, `.`, `#`, or a lowercase English letter.\n*   There is exactly one square represented as `S` and one square represented as `G`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$\n$a_{1,1}\\dots a_{1,W}$\n$\\vdots$\n$a_{H,1}\\dots a_{H,W}$"},{"iden":"sample input 1","content":"2 5\nS.b.b\na.a.G"},{"iden":"sample output 1","content":"4\n\nLet $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.  \nInitially, Takahashi is at $(1, 1)$. One way to reach $(2, 5)$ in four seconds is:\n\n*   go from $(1, 1)$ to $(2, 1)$;\n*   teleport from $(2, 1)$ to $(2, 3)$, which is also an `a` square;\n*   go from $(2, 3)$ to $(2, 4)$;\n*   go from $(2, 4)$ to $(2, 5)$."},{"iden":"sample input 2","content":"11 11\nS##...#c...\n...#d.#.#..\n..........#\n.#....#...#\n#.....bc...\n#.##......#\n.......c..#\n..#........\na..........\nd..#...a...\n.#........G"},{"iden":"sample output 2","content":"14"},{"iden":"sample input 3","content":"11 11\n.#.#.e#a...\n.b..##..#..\n#....#.#..#\n.#dd..#..#.\n....#...#e.\nc#.#a....#.\n.....#..#.e\n.#....#b.#.\n.#...#..#..\n......#c#G.\n#..S...#..."},{"iden":"sample output 3","content":"\\-1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}