10221 - 序言页码

一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值，一下是标准数字表:

I 1 L 50 M 1000 V 5 C 100 X 10 D 500

最多3个可以表示为10n的数字(I,X,C,M)可以连续放在一起，表示它们的和:

III=3 CCC=300 可表示为5x10n的字符(V,L,D)从不连续出现。

除了下一个规则，一般来说，字符以递减的顺序接连出现:

CCLXVIII = 100+100+50+10+5+1+1+1 = 268 有时，一个可表示为10^n的数出现在一个比它大的数前(I在V或X前面，X在L或C前面，等等)。在这种情况下，数值等于后面的那个数减去前面的那个数:

IV = 4 IX = 9 XL = 40 像XD, IC, 和XM这样的表达是非法的，因为前面的数比后面的数小太多。对于XD(490的错误表达)，可以写成 CDXC; 对于IC(99的错误表达)，可以写成XCIX; 对于XM(990的错误表达)，可以写成CMXC。

给定N(1 <= N < 3,500)， 序言的页码数，请统计在第1页到第N也中，有几个I出现，几个V出现，等等 (从小到大的顺序)。不要输出并没有出现过的字符。

比如N = 5, 那么页码数为: I, II, III, IV, V. 总共有7个I出现，2个V出现。

一个整数N。

每行一个字符和一个数字k，表示这个字符出现了k次。字符必须按数字表中的递增顺序输出。

Preface Numbering

A certain book's prefaces are numbered in upper case Roman numerals. Traditional Roman numeral values use a single letter to represent a certain subset of decimal numbers. Here is the standard set:

    I   1     L   50    M  1000
    V   5     C  100
    X  10     D  500

As many as three of the same marks that represent 10n may be placed consecutively to form other numbers:

III is 3 CCC is 300 Marks that have the value 5x10n are never used consecutively.

Generally (with the exception of the next rule), marks are connected together and written in descending order to form even more numbers:

CCLXVIII = 100+100+50+10+5+1+1+1 = 268 Sometimes, a mark that represents 10^n is placed before a mark of one of the two next higher values (I before V or X; X before L or C; etc.). In this case, the value of the smaller mark is SUBTRACTED from the mark it precedes:

IV = 4 IX = 9 XL = 40 This compound mark forms a unit and may not be combined to make another compound mark (e.g., IXL is wrong for 39; XXXIX is correct). Compound marks like XD, IC, and XM are not legal, since the smaller mark is too much smaller than the larger one. For XD (wrong for 490), one would use CDXC; for IC (wrong for 99), one would use XCIX; for XM (wrong for 990), one would use CMXC. 90 is expressed XC and not LXL, since L followed by X connotes that successive marks are X or smaller (probably, anyway).

Given N (1 <= N < 3,500), the number of pages in the preface of a book, calculate and print the number of I's, V's, etc. (in order from lowest to highest) required to typeset all the page numbers (in Roman numerals) from 1 through N. Do not print letters that do not appear in the page numbers specified.

If N = 5, then the page numbers are: I, II, III, IV, V. The total number of I's is 7 and the total number of V's is 2.

PROGRAM NAME: preface INPUT FORMAT A single line containing the integer N. SAMPLE INPUT (file preface.in) 5

OUTPUT FORMAT The output lines specify, in ascending order of Roman numeral letters, the letter, a single space, and the number of times that letter appears on preface page numbers. Stop printing letter totals after printing the highest value letter used to form preface numbers in the specified set. SAMPLE OUTPUT (file preface.out) I 7 V 2