Bạn và một số con quái vật đang ở trong một mê cung. Khi bạn di chuyển một bước theo một hướng bất kỳ, tất cả quái vật cũng có thể đồng thời di chuyển một bước.

Mục tiêu của bạn là thoát khỏi mê cung bằng cách tới một ô biên (ô ở rìa bản đồ), mà không bao giờ đứng chung một ô với bất kỳ quái vật nào.

Bạn cần xác định xem có thể thoát được hay không. Nếu có, hãy in ra một đường đi an toàn.

Lưu ý:

Kế hoạch di chuyển của bạn phải an toàn trong mọi tình huống.

Điều này có nghĩa là kể cả khi quái vật biết trước đường đi của bạn, chúng cũng không thể chặn được bạn.

Dữ liệu vào (Input):

Dòng đầu tiên chứa hai số nguyên n và m — chiều cao và chiều rộng của bản đồ.

Tiếp theo là n dòng, mỗi dòng có m ký tự mô tả mê cung:

. → Ô trống (có thể đi)

'#' → Tường (không thể đi)

A → Vị trí bắt đầu của bạn (duy nhất trong bản đồ)

M → Vị trí quái vật

*Dữ liệu ra: *

Nếu không có cách thoát, in ra:

NO

Ngược lại, in ra:

YES k path

Trong đó:

k → độ dài đường đi.

path → mô tả đường đi bằng các ký tự:

U → đi lên (Up)

D → đi xuống (Down)

L → đi sang trái (Left)

R → đi sang phải (Right)

Yêu cầu:

Bạn chỉ cần in ra một đường đi hợp lệ.

Độ dài đường đi không vượt quá n * m.

Ví dụ :

Input:

5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######

Output:

YES
5
RRDDR