Задачі
Roman numerals
Roman numerals
Roman numbers are based on seven symbols "\textbf{I}", "\textbf{V}", "\textbf{X}", "\textbf{L}", "\textbf{C}", "\textbf{D}" and "\textbf{M}". The "costs" of those symbols are \textbf{1},\textbf{5}, \textbf{10}, \textbf{50}, \textbf{100}, \textbf{500} and \textbf{1000}, respectively. To calculate decimal value of a Roman number, we will use the following algorithm:
\begin{enumerate}
\item Find the most significant (the most "expensive") symbol. If there are several such symbols take \textbf{the leftmost one}. Let the found symbol is placed in position \textbf{i}.
\item Denote as Middle the "cost" of symbol placed in position \textbf{i}.
\item Calculate the value of Roman number formed by the symbols, standing to the right of \textbf{i}. Denote this value as\textbf{Right}.
\item Calculate the value of Roman number formed by the numerals, standing to the left of \textbf{i}. Denote this value as\textbf{Left}.
\item Let \textbf{Middle + Right -- Left} be the value of a Roman number. Obviously, if we use this algorithm, the same number can be written in many ways. For example, the number \textbf{19} can be written as "\textbf{IXX}", "\textbf{XIX}", "\textbf{XVIV}", "\textbf{XVIIII}" and so on.
\end{enumerate}
Given decimal number \textbf{n} and Roman number \textbf{S}, you are to find such digits transposition of \textbf{S}, that represents \textbf{n} in Roman notation.
\InputFile
The first line contains an integer \textbf{n} in decimal notation. The second line contains a number \textbf{S} in Roman notation (\textbf{--50000} ≤ \textbf{n} ≤ \textbf{50000}, \textbf{1} ≤ \textbf{length(S)} ≤ \textbf{50}).
\OutputFile
The first line of output file should contain the Roman number or word "\textbf{NO}" (without the quotes) if there is no solution.
Вхідні дані #1
16 XXVI
Вихідні дані #1
VXXI