Cho một bản đồ hình chữ nhật gồm hàng và cột. Mỗi ô là một trong bốn ký hiệu:
#: tường, không thể đi qua;.: ô trống;- : vị trí bắt đầu;
- : vị trí đích.
Có đúng một ô và một ô . Từ một ô có thể đi sang ô chung cạnh ở bên trái, bên phải, phía trên hoặc phía dưới, miễn là ô mới không phải tường.
Hãy tìm một đường đi ngắn nhất từ tới . Nếu có nhiều đường ngắn nhất, có thể in bất kỳ đường nào.
Input
- Dòng đầu chứa hai số nguyên và .
- Mỗi trong dòng tiếp theo là một xâu gồm đúng ký tự mô tả bản đồ.
Output
- Nếu không có đường đi, in
NO. - Nếu có đường đi, in lần lượt:
- dòng đầu là
YES; - dòng thứ hai là độ dài đường đi;
- dòng thứ ba là xâu mô tả các bước, dùng tương ứng với trái, phải, lên, xuống.
Constraints
- .
- Bản đồ có đúng một và một .
Scoring
- Subtask ( số điểm): .
- Subtask ( số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
5 6 ###### #A...# ###.## #...B# ######
Output
YES 5 RRDDR
Giải thích: Xâu RRDDR đưa từ tới qua năm bước. Các bức tường buộc mọi đường hợp lệ phải dùng ít nhất năm bước.