#2034 · Cuộc Đua Săn Voucher

Cơ sở Thủ Đức HUTECH đang tổ chức một sự kiện lớn mang tên "Truy tìm kho báu" nhân dịp ngày hội chào hè 2026. Khuôn viên trường được chia thành một bản đồ dạng lưới tọa độ khổng lồ gồm H hàng (từ Bắc xuống Nam) và W cột (từ Tây sang Đông). Vị trí ở hàng thứ i và cột thứ j được gọi là ô (i,j).

Bạn bắt đầu xuất phát từ cổng chính của trường ở tọa độ (1,1) và đích đến cuối cùng là sân khấu trung tâm nằm ở tọa độ (H,W). Ban tổ chức đã rải sẵn N chiếc thẻ Voucher (có thể đổi lấy trà sữa hoặc áo thun của trường) tại các vị trí (R_i, C_i) khác nhau trên bản đồ.

Tuy nhiên, thời gian sự kiện có hạn nên giám thị có một quy định khắt khe: Từ ô hiện tại, bạn chỉ được phép bước sang ô bên phải (tiến về phía Đông, kí hiệu là R - Right) hoặc bước xuống ô bên dưới (tiến về phía Nam, kí hiệu là D - Down). Bạn không được phép đi ngược lại để tránh đụng trúng các đội chơi khác ở phía sau.

Là sinh viên tham gia giải đấu, bạn không muốn đi mò mẫm. Bạn quyết định viết một thuật toán để tìm ra lộ trình di chuyển từ (1,1) đến (H,W) sao cho thu thập được nhiều thẻ Voucher nhất có thể. Đồng thời, chương trình cũng phải in ra luôn cả "bản đồ chỉ đường" (chuỗi hành động) để bạn và đồng đội cứ thế mà chạy theo.

• Dòng đầu tiên chứa 3 số nguyên H,W (kích thước khuôn viên trường, 2≤H,W≤2×10^5) và N (số lượng Voucher, tối đa 2×10^5).
• N dòng tiếp theo, mỗi dòng chứa tọa độ (R_i, C_i) của một chiếc Voucher. Đảm bảo không có thẻ nào nằm ở vị trí xuất phát (1,1) hoặc đích đến (H,W).

In ra 2 dòng:

• Dòng 1: Một số nguyên duy nhất là số lượng thẻ Voucher nhiều nhất bạn có thể nhặt được.
• Dòng 2: Một chuỗi ký tự có độ dài chính xác là H+W−2 bao gồm toàn các ký tự D (đi xuống) và R (đi sang phải) thể hiện lộ trình di chuyển tối ưu đó.

Lưu ý: Nếu có nhiều lộ trình cùng thu được lượng Voucher tối đa như nhau, bạn in ra lộ trình nào cũng được