Để phục vụ cho việc giảng dạy môn Tin học, trường TH True School đã mua một con rô-bốt có thể lập trình được. Con rô-bốt này có thể hoạt động trên một bảng gồm ~n × m~ ô, một số ô có thể có chướng ngại vật. Trên bảng có một ô ghi chữ ’S’ là ô xuất phát của rô-bốt và một ô ghi chữ ’G’ là ô đích của rô-bốt. Con rô-bốt có thể được điều khiển bởi một dãy lệnh gồm các chữ cái ’U’, ’D’, ’L’, ’R’ lần lượt có ý nghĩa là điều khiển con rô-bốt sang ô phía trên, ô phía dưới, ô bên trái, ô bên phải ô nó đang đứng. Con rô-bốt sẽ bỏ qua một lệnh nếu lệnh đó khiến nó đi ra ngoài bảng, hoặc đi vào ô có chướng ngại vật. Nếu rô-bốt đến được ô đích, nó sẽ tự động ngắt điện và bỏ qua các lệnh mà mình chưa thực hiện.

Các học sinh của trường TH đã viết được một dãy lệnh để điều khiển rô-bốt, tuy nhiên do họ mới bắt đầu học lập trình, dãy lệnh họ viết ra có thể không đưa rô-bốt đến ô đích. Bạn có nhiệm vụ viết chương trình sửa lại dãy lệnh do học sinh viết ra sao cho dãy lệnh sau khi sửa sẽ giúp rô-bốt đi từ ô xuất phát đến ô đích. Để tránh làm các học sinh trường TH bị tổn thương (họ có tâm hồn khá mong manh dễ vỡ), chương trình của bạn chỉ được chỉnh sửa dãy lệnh bằng các thao tác chỉnh sửa đã được quy định sẵn, và số lượng thao tác chỉnh sửa bạn sử dụng phải là ít nhất. Các thao tác chỉnh sửa bạn có thể sử dụng là xóa một lệnh nào đó trong dãy lệnh, hoặc chèn thêm một lệnh vào trong dãy lệnh.

Trong bài này, để người ra đề không phải viết trình chấm cho đỡ mất công, bạn chỉ cần in ra số lượng thao tác chỉnh sửa ít nhất cần sử dụng để dãy lệnh sau khi chỉnh sửa có thể đưa rô-bốt từ ô xuất phát đến ô đích.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m (1 ≤ m, n ≤ 50)~ lần lượt là số lượng cột và hàng của bảng hoạt động của rô-bốt.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ kí tự mô tả bảng hoạt động. Kí tự ’S’ mô tả ô xuất phát của rô-bốt, kí tự ’G’ mô tả ô đích của rô-bốt, kí tự ’.’ mô tả ô trống và kí tự ’#’ mô tả ô có chướng ngại vật. Dữ liệu đảm bảo luôn có đường đi từ ô xuất phát đến ô đích.
• Dòng thứ ~n + 2~ chứa một xâu có độ dài trong đoạn từ 1 đến 50 là dãy lệnh mà học sinh trường TH viết.

Output

• In ra một dòng duy nhất chứa một số nguyên là số lượng thao tác chỉnh sửa ít nhất cần sử dụng.

Sample

Input #1

2 6
....#S
.#..G.
RRDURLURDRUDDRLRDLUUUDLUDURDRDLLRRLUUDUR

Output #1

0

Problem source: Kc97ble - Free Contest 41