Đường đi ít số 0 nhất

Cho một bảng vuông kích thước $N\times N$ gồm các số nguyên không âm.

Một đường đi bắt đầu ở ô góc trên bên trái, kết thúc ở ô góc dưới bên phải, và tại mỗi bước chỉ được di chuyển sang ô bên phải hoặc ô bên dưới ô hiện tại.

Hãy tìm đường đi sao cho tích của tất cả các số nằm trên đường đi đó có ít chữ số 0 ở tận cùng nhất.

Lưu ý bảng có thể chứa số $0$. Nếu đường đi chứa ít nhất một ô mang giá trị $0$ thì tích bằng $0$, và số $0$ được viết là "0" nên có đúng $1$ chữ số 0 ở tận cùng.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$ là kích thước của bảng.
• $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên mô tả các phần tử của bảng.

Dữ liệu ra

• Dòng đầu tiên in ra số chữ số 0 ở tận cùng ít nhất có thể đạt được.
• Dòng thứ hai in ra đường đi tương ứng dưới dạng một xâu gồm $2N-2$ ký tự, trong đó ký tự D nghĩa là đi xuống dưới và ký tự R nghĩa là đi sang phải.

Nếu có nhiều đường đi cùng đạt kết quả tối ưu, in ra một đường đi bất kỳ trong số đó.

Ràng buộc

• $2\le N\le 1000$
• $0\le a_{i,j}\le {10}^9$

Ví dụ