Quái vật

Cho một mê cung hình chữ nhật kích thước \(n \times m\), gồm các ô trống (kí hiệu .), tường (#), người chơi (A) và quái vật (M).

Người chơi có thể di chuyển sang một trong bốn ô kề (trên, dưới, trái, phải) mỗi bước, nhưng không được đi xuyên qua tường hoặc ra ngoài mê cung. Quái vật cũng di chuyển tương tự, với tốc độ bằng người chơi: mỗi lượt, tất cả các con quái đều tiến thêm một bước.

Bạn cần tìm một đường đi để người chơi thoát ra khỏi mê cung trước khi bị quái vật bắt. Người chơi coi như bị bắt nếu đi vào một ô mà quái vật có thể tới được cùng thời điểm hoặc sớm hơn.

Một lối thoát là bất kỳ ô nào nằm ở viền của mê cung (người chơi thoát ngay khi đứng ở ô viền).

Hãy xác định xem người chơi có thể thoát hay không. Nếu có, in ra đường đi ngắn nhất; nếu có nhiều đường đi ngắn nhất, in ra đường đi có xâu mô tả nhỏ nhất theo thứ tự từ điển.

Input

Dòng đầu chứa hai số nguyên \(n, m\) (\(1 \le n, m \le 1000\)).

Tiếp theo là \(n\) dòng, mỗi dòng \(m\) ký tự, mô tả mê cung. Mỗi ký tự là một trong:

• # — tường;
• . — ô trống;
• A — vị trí người chơi (xuất hiện đúng 1 lần);
• M — vị trí của một quái vật (có thể nhiều hoặc không có).

Output

Nếu không thể thoát, in ra NO.

Ngược lại, in ra ba dòng:

• Dòng 1: YES;
• Dòng 2: độ dài \(L\) của đường đi ngắn nhất;
• Dòng 3: xâu gồm \(L\) ký tự mô tả đường đi, dùng D, U, L, R tương ứng với đi xuống, lên trên, sang trái, sang phải. Trong các đường đi ngắn nhất, chọn xâu nhỏ nhất theo thứ tự từ điển (D < L < R < U). Nếu \(L = 0\) (người chơi đã ở viền), dòng này để trống.

Notes

Với mê cung

########
#M..A..#
#.#.M#.#
#M#..#..
#.######

người chơi thoát được sau \(5\) bước theo đường đi RRDDR.