{"problem":{"name":"Third Avenue","description":{"content":"There is a town represented as a two-dimensional grid with $H$ horizontal rows and $W$ vertical columns.   A character $a_{i,j}$ describes the square at the $i$\\-th row from the top and $j$\\-th column","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc184_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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`.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc184_e","tags":[],"sample_group":[["2 5\nS.b.b\na.a.G","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)$."],["11 11\nS##...#c...\n...#d.#.#..\n..........#\n.#....#...#\n#.....bc...\n#.##......#\n.......c..#\n..#........\na..........\nd..#...a...\n.#........G","14"],["11 11\n.#.#.e#a...\n.b..##..#..\n#....#.#..#\n.#dd..#..#.\n....#...#e.\nc#.#a....#.\n.....#..#.e\n.#....#b.#.\n.#...#..#..\n......#c#G.\n#..S...#...","\\-1"]],"created_at":"2026-03-03 11:01:14"}}