Phố thứ ba

Cho một lưới hình chữ nhật gồm \(H\) hàng và \(W\) cột. Ký tự \(a_{i,j}\) của ô ở hàng \(i\) (tính từ trên xuống) và cột \(j\) (tính từ trái sang) thuộc một trong các loại sau: S, G, ., \#, hoặc một chữ cái thường a..z. Dấu \# là ô cấm vào, a..z là các ô có cổng dịch chuyển.

Bạn đứng tại ô ký hiệu S và muốn đến ô ký hiệu G. Trong một bước, bạn có thể:

• Di chuyển sang một trong bốn ô kề trực tiếp (lên, xuống, trái, phải) nếu ô đó không phải \#;
• Nếu đang đứng trên một ô mang chữ cái c nào đó, bạn có thể dịch chuyển tới bất kỳ ô mang đúng chữ c khác bất kể vị trí.

Hãy tính số bước ít nhất để đi từ S đến G. Nếu không thể đi được, in -1.

Input

Dòng đầu chứa hai số nguyên \(H, W\) (\(1 \le H, W \le 2000\)).

\(H\) dòng tiếp theo, mỗi dòng là một xâu dài \(W\) ký tự mô tả lưới.

Bảo đảm có đúng một S và đúng một G. Các ký tự còn lại thuộc tập ., \#, a..z.

Output

In ra một số nguyên — số bước ngắn nhất cần thiết, hoặc -1 nếu không thể tới G.

Scoring

• Có \(50\%\) số điểm ứng với \(H, W \le 50\).

Sample Input 1

2 5
S.b.b
a.a.G

Sample Output 1

4

Sample Input 2

11 11
S##...#c...
...#d.#.#..
..........#
.#....#...#
#.....bc...
#.##......#
.......c..#
..#........
a..........
d..#...a...
.#........G

Sample Output 2

14