Chìa khóa và cửa

Một robot đứng ở ô S của bản đồ $n$ hàng, $m$ cột và cần đến ô T. Các ký tự trên bản đồ:

• . là ô trống, # là tường, S và T cũng là ô trống;
• chữ thường a đến f là ô có chìa khóa: khi robot bước vào ô này, nó nhặt chìa và giữ mãi mãi (chìa không mất đi khi mở cửa);
• chữ hoa A đến F là cửa: robot chỉ được bước vào ô cửa A nếu đang giữ chìa a, tương tự với các chữ khác.

Mỗi bước robot đi sang một ô chung cạnh (lên, xuống, trái, phải), không ra khỏi bản đồ và không vào tường. Hãy tìm số bước ít nhất để robot đến T, hoặc in $-1$ nếu không thể.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n,m$.
• $n$ dòng tiếp theo, mỗi dòng là một xâu độ dài $m$ gồm các ký tự đã mô tả. Có đúng một S và đúng một T.

Dữ liệu ra

In một số nguyên: số bước ít nhất, hoặc $-1$.

Ràng buộc

• $1\le n,m\le 60$, $n·m\ge 2$
• Mỗi loại chìa và mỗi loại cửa có thể xuất hiện nhiều lần hoặc không xuất hiện.

Ví dụ