📖 Bài giảng & lời giải: đây là Bài tập 7 trong bài giảng Thuật toán qua trò chơi 4: Game 2048 trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cho bàn 2048 kích thước $n \times n$ (mỗi ô là 0 hoặc một lũy thừa của 2); không sinh ô mới sau mỗi lần bấm. Người chơi muốn đi hai nước liên tiếp sao cho tổng điểm gộp của hai nước là lớn nhất. Cả hai nước đều phải là nước đi được (làm bàn thay đổi); riêng trường hợp sau nước thứ nhất không còn hướng nào đi được thì chỉ tính điểm của nước thứ nhất.

Luật trượt và gộp của 2048 (mô tả cho phím ←, các phím khác tương tự theo hướng tương ứng): trên mỗi hàng, các ô khác 0 được dồn hết về mép trái, giữ nguyên thứ tự. Xét các ô đó lần lượt từ mép trái (mép đích) đi ra: nếu hai ô liền nhau có cùng giá trị $x$ thì chúng gộp thành một ô $2x$ và người chơi được cộng $2x$ điểm. Mỗi ô chỉ được tham gia gộp nhiều nhất một lần trong một lần bấm (ô vừa gộp xong bị "khoá"), và cặp nào gần mép đích hơn thì được gộp trước. Ví dụ hàng 2 2 2 2 bấm ← thành 4 4 0 0 (+8 điểm), hàng 4 4 8 0 bấm ← thành 8 8 0 0 (+8 điểm, ô 8 mới không gộp tiếp với ô 8 cũ).

Nói cách khác, với mỗi hướng đi được $d_1$, giá trị của $d_1$ là điểm của $d_1$ cộng với điểm lớn nhất của một nước đi được $d_2$ trên bàn sau $d_1$ (cộng 0 nếu không có $d_2$ nào). Hãy in ra hướng $d_1$ có giá trị lớn nhất và giá trị đó; nếu bằng nhau thì chọn hướng đứng trước trong thứ tự L U R D.

Dữ liệu vào

• Dòng 1: số nguyên $n$ ($2 \le n \le 100$).
• $n$ dòng tiếp theo, mỗi dòng $n$ số nguyên, mỗi số là $0$ hoặc $2^t$ với $1 \le t \le 30$.

Kết quả

In ra ký tự hướng $d_1$ và tổng điểm lớn nhất, cách nhau một dấu cách. Nếu không có nước nào đi được thì in NONE.

Sample Input

4
2 2 4 0
0 0 0 8
0 0 0 0
0 0 0 0

Sample Output

L 12