일반화된 로마 숫자

로마 사람들은 I, V, X, L, C로 각각 1, 5, 10, 50, 100을 나타냈다. XXXVII은 $10+10+10+5+1+1$이므로 37이다. 문자는 보통 큰 것부터 작아지는 순서로 적지만, 작은 문자 하나를 큰 문자 앞에 두면 큰 값에서 작은 값을 뺀다. 그래서 IV는 4, IX는 9, XL은 40, XC는 90이고, 94는 XCIV로 적는다.

VIC는 전통적인 로마 숫자가 아니지만 94를 적는 또 다른 방법으로 읽을 수 있다. VI가 6이므로 VIC는 $100-6$이다. 일반적으로 두 식 $a$와 $b$의 값이 각각 $v(a)$, $v(b)$일 때, $v(a) \ge v(b)$이면 $v(ab) = v(a) + v(b)$이고, 그렇지 않으면 $v(ab) = v(b) - v(a)$이다.

이 규칙에는 모호함이 있다. 계산 순서가 달라지면 값도 달라지기 때문이다. IVX를 보자. IV가 4이고 X가 10이므로 이 순서로는 IVX가 6이다. 반면 I가 1이고 VX가 5이므로 저 순서로는 IVX가 4이다. 순서를 정하려고 괄호를 붙일 수 있다. 문자열이 주어지면 괄호를 붙이는 방법을 바꿔 얻을 수 있는 값을 모두 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 줄에는 I, V, X, L, C로만 이루어진 문자열이 하나씩 주어지며, 길이는 1 이상 50 이하다. 0 하나만 있는 줄이 나오면 입력이 끝난다.

테스트 케이스마다 Case i: v1 v2 ... 형식으로 한 줄씩 출력한다. $i$는 1부터 세는 테스트 케이스 번호이고, $v_1, v_2, \dots$는 괄호를 붙여 얻을 수 있는 서로 다른 값을 증가하는 순서로 나열한 것이다. 값 사이는 공백 하나로 구분한다.