Trong mê cung có một chiếc bánh mà bạn rất muốn ăn. Bản đồ mê cung là một lưới gồm \(R\) hàng và \(C\) cột. Mỗi ô chứa một trong bốn ký tự:

• #: một khối tường.
• .: một ô trống.
• S: ô trống tại vị trí ban đầu của bạn.
• C: ô trống chứa chiếc bánh.

Bạn chỉ được đi trên các ô trống, và có thể đi từ một ô sang một ô trống có chung cạnh với nó. Toàn bộ vùng hình chữ nhật trên bản đồ được bao quanh bởi các khối tường.

Để đến chiếc bánh nhanh hơn, bạn có một khẩu súng tạo cổng của Aperture Science™. Bất kỳ lúc nào, bạn có thể bắn một cổng theo một trong bốn hướng lên, trái, xuống hoặc phải. Cổng bay theo hướng đó cho đến khi gặp khối tường đầu tiên, rồi xuất hiện trên mặt của khối tường hướng về phía bạn.

Tại mỗi thời điểm chỉ có tối đa hai cổng. Nếu đã có hai cổng, ngay khi bắn thêm một cổng, bạn phải chọn một trong hai cổng cũ để xóa. Bắn vào vị trí đang có cổng sẽ thay thế cổng đó: mỗi mặt của một khối tường có tối đa một cổng. Hai mặt khác nhau của cùng một khối tường có thể cùng chứa cổng.

Khi có hai cổng, bạn có thể dùng chúng để dịch chuyển. Đứng ở ô trống ngay cạnh một cổng, bạn có thể bước vào cổng đó và xuất hiện ở ô trống ngay cạnh cổng còn lại. Việc này mất thời gian bằng một bước đi giữa hai ô kề cạnh.

Việc bắn cổng không tốn thời gian. Mỗi bước đi giữa hai ô kề cạnh hoặc mỗi lần dịch chuyển qua cổng tốn một đơn vị thời gian.

Cho bản đồ mê cung, vị trí ban đầu và vị trí chiếc bánh, hãy tính thời gian ít nhất để đến chiếc bánh.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(R,C\), lần lượt là số hàng và số cột của bản đồ.

\(R\) dòng tiếp theo mô tả bản đồ; mỗi dòng gồm đúng \(C\) ký tự thuộc tập #, ., S, C. Mỗi ký tự S và C xuất hiện đúng một lần.

Dữ liệu ra

In một số nguyên: thời gian ít nhất để đi từ vị trí ban đầu đến chiếc bánh. Dữ liệu bảo đảm có thể đến được chiếc bánh.

Ràng buộc

• \(1 \le R,C \le 1000\).
• Có đúng một vị trí ban đầu và một vị trí chiếc bánh.
• Có thể đi từ vị trí ban đầu đến chiếc bánh.

Phân nhóm

1. 11 điểm: \(1 \le R \le 10\), \(1 \le C \le 10\).
2. 20 điểm: \(1 \le R \le 50\), \(1 \le C \le 50\).
3. 20 điểm: \(1 \le R \le 200\), \(1 \le C \le 200\). Mỗi ô trống có ít nhất một khối tường kề cạnh.
4. 19 điểm: \(1 \le R \le 200\), \(1 \le C \le 200\).
5. 30 điểm: \(1 \le R \le 1000\), \(1 \le C \le 1000\).

Ví dụ

4 4
.#.C
.#.#
....
S...

4