숫자 압축

시간 제한1초메모리 제한128 MB

요약

F < R인 두 수의 쌍이 주어질 때, R로 복원되는 가장 짧은 압축 형태 C를 F-와 함께 출력한다.

문제

자릿수를 줄여 저장하는 문제입니다.

한 실험 물리학자가 실험에서 매우 많은 데이터를 만들어 냅니다. 이 데이터에는 특별한 성질이 있어서, 그는 이 성질을 이용해 결과를 저장하는 데 필요한 공간을 줄이려고 합니다.

데이터는 두 수의 쌍으로 생성되며, 앞의 수는 항상 뒤의 수보다 작습니다. 그는 책에서 쪽 범위를 줄여 쓰는 방식과 비슷하게 각 쌍을 저장하고 싶어 합니다. 예를 들어 "11쪽부터 18쪽까지"를 "11-8"처럼 줄여 쓰는 식입니다.

기호 정의

압축된 뒤 수를 복원하는 규칙

규칙	예시
$C$ 는 항상 가능한 한 적은 자릿수로 씁니다.
$C > F$ 이면 $R = C$ 입니다.	"123-283"이면 $F = 123$ , $C = 283$ 이므로 $R = 283$
$C \le F$ 이면 아래 규칙을 적용합니다.
$\text{LSD}(\text{len}(C), R)$ 는 항상 $C$ 와 같습니다.
$\text{LSD}(\text{len}(C), F) < C$ 이면, $R$ 은 $\text{MSD}(\text{len}(F) - \text{len}(C), F)$ 뒤에 $C$ 의 자릿수를 이어 붙인 값입니다.	"4137-223"이면 $F = 4137$ , $C = 223$ ; $\text{MSD}(1, 4137) = 4$ 이므로 $R = 4223$
$\text{LSD}(\text{len}(C), F) \ge C$ 이면, $R$ 은 $\text{MSD}(\text{len}(F) - \text{len}(C), F)$ 뒤에 $C$ 를 이어 붙인 값에 $10^{\text{len}(C)}$ 을 더한 값입니다.	"8543-13"이면 $F = 8543$ , $C = 13$ ; $\text{MSD}(2, 8543) = 85$ 이므로 $R = 8513 + 100 = 8613$

$C$ 의 앞자리 $0$ 은 의미가 있습니다. "7", "07", "007"은 모두 서로 다릅니다. 예를 들면 다음과 같습니다.

이 문제에서 여러분이 할 일은 복원의 반대입니다. 압축되지 않은 각 쌍 $F$ 와 $R$ 이 주어질 때, 가능한 한 적은 자릿수로 압축한 뒤 수 $C$ 를 출력하세요.

각 줄에는 하이픈으로 구분된 음이 아닌 두 정수의 쌍이 주어집니다. 뒤의 수는 항상 앞의 수보다 크며, 뒤의 수는 항상 $2^{31} - 1$ 보다 작습니다. 입력은 파일의 끝까지 계속됩니다.

입력의 각 줄마다 한 줄씩, 앞의 수와 하이픈, 그리고 압축한 뒤 수를 이어서 출력합니다.

예제 1

입력

10-18
83294-84137
100-200

예상 출력

10-8
83294-137
100-00

예제 2

입력

123-283
4137-4223
8543-8613

예상 출력

123-283
4137-23
8543-13