Римські цифри

Римські цифри базуються на семи символах: "I", "V", "X", "L", "C", "D" та "M". Значення цих символів дорівнюють $1$, $5$, $10$, $50$, $100$, $500$ і $1000$ відповідно. Щоб обчислити десяткове значення римської цифри, використовуйте наступний алгоритм:

1. Знайдіть найзначиміший ("найцінніший") символ. Якщо таких символів кілька, оберіть найлівіший із них. Нехай цей символ стоїть на позиції i.

2. Позначте як Middle значення символу на позиції i.

3. Обчисліть значення римської цифри, утвореної символами праворуч від i. Позначте це значення як Right.

4. Обчисліть значення римської цифри, утвореної символами ліворуч від i. Позначте це значення як Left.

5. Значення римської цифри дорівнює Middle + Right – Left. Як видно, використовуючи цей алгоритм, одне й те саме число можна записати багатьма способами. Наприклад, число $19$ можна записати як "IXX", "XIX", "XVIV", "XVIIII" тощо.

Дано десяткове число $n$ та римську цифру $S$. Знайдіть таку перестановку символів у $S$, яка відповідатиме числу $n$ у римському записі.