Romeo tìm Juliet 2

Hầm mộ nơi Juliet nằm là một lưới gồm \(m\) dòng và \(n\) cột. Mỗi ô là phòng trống hoặc phòng có quỷ dữ. Từ một phòng có thể sang phòng chung cạnh (trên, dưới, trái, phải); không được bước vào phòng có quỷ.

Lần này Romeo không chỉ muốn biết có đến được phòng Juliet hay không, mà cần một lộ trình cụ thể đi qua các phòng trống để chàng đến nơi thật nhanh. Hãy in ra lộ trình ngắn nhất từ phòng Romeo đến phòng Juliet. Nếu có nhiều lộ trình ngắn nhất, chọn lộ trình có dãy toạ độ (dòng, cột) nhỏ nhất theo thứ tự từ điển, tức là ở mỗi bước chọn ô kế tiếp có dòng nhỏ hơn, nếu bằng nhau thì có cột nhỏ hơn (so sánh dãy ô từ ô đầu tiên trở đi).

Input

• Dòng đầu tiên: hai số nguyên \(m\), \(n\).
• \(m\) dòng tiếp theo, mỗi dòng là xâu gồm \(n\) ký tự không có khoảng trắng: o là phòng trống, x là phòng có quỷ, R là phòng Romeo, J là phòng Juliet (mỗi loại R, J đúng một ô).

Output

• Nếu không đến được: in NO.
• Ngược lại in:
• dòng 1: YES;
• dòng 2: số ô của lộ trình (tính cả ô của Romeo và ô của Juliet);
• các dòng tiếp theo: toạ độ dòng cột (đánh số từ 1) của các ô trên lộ trình, bắt đầu từ ô của Romeo và kết thúc ở ô của Juliet, mỗi ô một dòng.

Constraints

• \(1 \le m, n \le 500\)
• R và J là hai ô khác nhau và đều không có quỷ.

Sample Input 1

4 5
Rooxo
oxooo
oxxxo
ooooJ

Sample Output 1

YES
8
1 1
1 2
1 3
2 3
2 4
2 5
3 5
4 5

Sample Input 2

3 4
Rxoo
oxxJ
ooxo

Sample Output 2

NO

Explanation

Ở ví dụ 1 có hai lộ trình ngắn nhất: đi vòng phía trên hoặc đi xuống cột 1 rồi sang phải dọc hàng cuối. Lộ trình đầu có ô thứ hai là \((1,2)\) nhỏ hơn \((2,1)\) nên được chọn.