Bạn được cho một bảng kích thước \(n \times m\). Mỗi ô trên bảng chứa một trong các ký tự sau:

• .: ô trống.
• #: tường.
• a\(–\)f: chìa khóa.
• A\(–\)F: cửa bị khóa.

Người chơi có thể di chuyển sang một trong bốn ô kề cạnh (lên, xuống, trái, phải) và không được đi vào tường. Để đi qua cửa A, người chơi phải thu thập được chìa khóa a; tương tự với các cặp B\(–\)b\(, ...,\) F\(–\)f.

Hãy xác định số bước đi ít nhất để đi từ điểm \((1, 1)\) đến điểm \((n, m)\) (dữ liệu luôn đảm bảo điểm bắt đầu và kết thúc là ô trống). Nếu không thể đến được đích, hãy in ra \(-1\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\) (\(1 \le n, m \le 100\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa một xâu độ dài \(m\) mô tả bảng.

Output

• In ra một số nguyên duy nhất là số bước đi ít nhất để đi từ điểm \((1, 1)\) đến điểm \((n, m)\). Nếu không tồn tại đường đi hợp lệ, in ra \(-1\).

Example

5 6
....#.
##Aa#.
.#.#..
......
......

11