prithivMLmods/Coder-Stat

1 2 3<h1><font color="#000">Problem C:</font> Numeral System</h1>4 5 6<p>7Prof. Hachioji has devised a new numeral system of8integral numbers with four lowercase letters "m", "c", "x", "i"9and with eight digits "2", "3", "4", "5", "6", "7", "8", "9". 10He doesn't use digit "0" nor digit "1" in this system.11</p>12 13 14<p>15The letters "m", "c", "x" and "i" correspond to 1000, 100, 10 and 1,16respectively, 17and the digits "2", ...,"9" correspond to 2, ..., 9, respectively.18This system has  nothing to do with the Roman numeral system.19</p>20 21 22<p>23For example,24character strings25</p>26<blockquote>27    "5m2c3x4i", "m2c4i"  and   "5m2c3x"28</blockquote>29<p>30correspond to the integral numbers 315234 (=5*1000+2*100+3*10+4*1),321204 (=1000+2*100+4*1),33 and 5230 (=5*1000+2*100+3*10), 34respectively.  35The parts of strings in the above example, "5m", "2c", "3x" and "4i" 36represent 5000 (=5*1000), 200 (=2*100), 30 (=3*10) and 4 (=4*1),37respectively. 38</p>39 40 41<p>42Each of the letters "m", "c", "x" and "i" may43 be prefixed by one of the digits44"2", "3", ..., "9". 45In that case, the prefix digit and the letter are regarded 46as a pair.47A pair that consists of a prefix digit and a letter 48corresponds to an integer that is equal to49the original value of the letter multiplied by 50the value of the prefix digit.51</p>52 53 54<p>55For each letter "m", "c", "x" and "i", 56the number of its occurrence in a string is at most one.57When it has a prefix digit, it should appear together with the prefix digit.58The letters "m", "c", "x" and "i" must appear in this order, from left to right.59Moreover, when a digit exists in a string,60it should appear as the prefix digit of the following letter.61Each letter may be omitted in a string, but62the whole string must not be empty.63A string made in this manner is called an <I>MCXI-string</I>.64</p>65 66 67<p>68An MCXI-string corresponds to a positive integer 69that is the sum of the values of the letters70and those of the pairs contained in it as mentioned above. 71The positive integer corresponding to an MCXI-string is called its72MCXI-value.73Moreover, given an integer from 1 to 9999,74there is a unique MCXI-string whose MCXI-value is equal 75to the given integer.76For example,77the MCXI-value of an MCXI-string "m2c4i" is 781204 that is equal to <tt>1000 + 2*100 + 4*1</tt>.79There are no MCXI-strings but "m2c4i" that correspond to 1204.80Note81that strings "1m2c4i", "mcc4i", "m2c0x4i", and "2cm4i" are82not valid MCXI-strings. 83The reasons are use of "1",84multiple occurrences of "c", use of "0", and the wrong order of "c" and "m",85respectively.86</p>87 88 89<p>90Your job is to write a program for Prof. Hachioji91that reads two MCXI-strings, 92computes the sum of their MCXI-values, and93prints the MCXI-string corresponding to the result.94</p>95 96 97<h2>Input</h2>98 99 100<p>101The input is as follows.102The first line contains a positive integer <I>n</I> (<= 500) that 103indicates the number of the following lines.  104The <I>k</I>+1 th line is the specification of 105the <I>k</I> th computation (<I>k</I>=1, ..., <I>n</I>).106</p>107 108 109<blockquote>110<I>n</I>                                    <br>111<I>specification</I><sub>1</sub>            <br>112<I>specification</I><sub>2</sub>            <br>113    ...<br>                   114<I>specification</I><sub><I>n</I></sub>     <br>115</blockquote>116 117 118<p>119Each specification is described in a line:120<blockquote>121<I>MCXI-string</I><sub>1</sub> <I>MCXI-string</I><sub>2</sub>122</blockquote>123<p>124The two MCXI-strings are separated by a space.125</p>126 127 128<p>129You may assume that the sum of the two MCXI-values 130of the two MCXI-strings in each specification 131is less than or equal to 9999. 132</p>133 134 135<h2>Output</h2>136 137 138<p>139For each specification,140your program should print an MCXI-string in a line.141Its MCXI-value should be the sum of the two MCXI-values142of the MCXI-strings in the specification.143No other characters should appear in the output.144</p>145 146 147<h2>Sample Input</h2>148<pre>14910150xi x9i151i 9i152c2x2i 4c8x8i153m2ci 4m7c9x8i1549c9x9i i155i 9m9c9x8i156m i157i m158m9i i1599m8c7xi c2x8i160</pre>161 162 163<h2>Output for the Sample Input</h2>164<pre>1653x166x1676cx1685m9c9x9i169m1709m9c9x9i171mi172mi173mx1749m9c9x9i175</pre>176 177 178 179 180