Người La Mã cổ đại sử dụng hệ thống chữ số đặc biệt gồm 7 ký hiệu sau để biểu diễn các số:

Số La Mã được hình thành bằng cách kết hợp các ký hiệu theo một số quy tắc sau:</p>

• Với các số không bắt đầu bằng 4 hoặc 9, chọn ký hiệu có giá trị lớn nhất mà không vượt quá số cần đổi, ghi ký hiệu đó và trừ giá trị tương ứng khỏi số đang xét. Lặp lại cho đến khi hết số.
• Với các số bắt đầu bằng 4 hoặc 9, sử dụng dạng trừ (subtractive form), tức là lấy ký hiệu đứng trước ký hiệu lớn hơn. Ví dụ:
  • 4 → IV (1 nhỏ hơn 5)
  • 9 → IX (1 nhỏ hơn 10)
  • 40 → XL (10 nhỏ hơn 50)
  • 90 → XC (10 nhỏ hơn 100)
  • 400 → CD (100 nhỏ hơn 500)
  • 900 → CM (100 nhỏ hơn 1000)

  Lưu ý

  • Các ký hiệu I, X, C, M có thể lặp lại tối đa 3 lần.
  • Các ký hiệu V, L, D không được lặp lại nhiều hơn 1 lần liên tiếp.

  Yêu cầu

  Viết chương trình nhận đầu vào là một số nguyên n (1 ≤ n ≤ 3999), xuất ra chuỗi biểu diễn số đó theo số La Mã.

  Ví dụ

  Input: 3749
  Output: MMMDCCXLIX
  Giải thích: 3000 = MMM, 700 = DCC, 40 = XL, 9 = IX

  Input: 58
  Output: LVIII
  Giải thích: 50 = L, 5 = V, 3 = III