Compress

Time limit1sMemory limit128 MB

Summary

Given pairs F and R with F < R, print F and the shortest compressed form C that decodes back to R.

Level: Medium4 of 10
Topics: String, Implementation, Math
Solved: No attempts yet

Problem

Reduce the number of digits.

An experimental physicist generates a huge amount of data. The data has a special property, and he wants to exploit it to shrink the space needed to store the results.

The data comes as pairs of numbers where the first number is always smaller than the second. He wants to store each pair much the way people abbreviate a range of pages in a book: instead of writing "pages 11 through 18" they sometimes write "11-8".

Notation

Symbol	Meaning	Example
$F$	the first number of a pair	in "18482-02", $F = 18482$
$C$	the second number in compressed form	in "18482-02", $C = 02$
$R$	the second number in decoded (original) form	in "18482-02", $R = 18502$
$\text{MSD}(x, y)$	the $x$ most significant digits of $y$ in base ten; the empty string when $x \le 0$	$\text{MSD}(3, 19283) = 192$ , $\text{MSD}(0, 12)$ is empty
$\text{LSD}(x, y)$	the $x$ least significant digits of $y$ in base ten, left-padded with zeros when needed	$\text{LSD}(2, 48290) = 90$ , $\text{LSD}(2, 3) = 03$

Decoding a compressed second number

Rule	Example
$C$ is always written with the fewest possible digits.
If $C > F$ , then $R = C$ .	for "123-283": $F = 123$ , $C = 283$ , so $R = 283$
If $C \le F$ , apply the rules below.
$\text{LSD}(\text{len}(C), R)$ always equals $C$ .
If $\text{LSD}(\text{len}(C), F) < C$ , then $R$ is $\text{MSD}(\text{len}(F) - \text{len}(C), F)$ followed by the digits of $C$ .	for "4137-223": $F = 4137$ , $C = 223$ ; $\text{MSD}(1, 4137) = 4$ , so $R = 4223$
If $\text{LSD}(\text{len}(C), F) \ge C$ , then $R$ is $10^{\text{len}(C)}$ plus $\text{MSD}(\text{len}(F) - \text{len}(C), F)$ followed by the digits of $C$ .	for "8543-13": $F = 8543$ , $C = 13$ ; $\text{MSD}(2, 8543) = 85$ , so $R = 8513 + 100 = 8613$

Leading zeros in $C$ are significant: "7", "07" and "007" are all different. For example:

for "2839-06": $F = 2839$ , $C = 06$ , so $R = 2906$
for "2839-006": $F = 2839$ , $C = 006$ , so $R = 3006$

Your task is the reverse of decoding: given each uncompressed pair $F$ and $R$ , output the compressed second number $C$ using the fewest possible digits.

Input

Each line contains a pair of non-negative integers separated by a hyphen. The second number is always larger than the first, and the second number is always less than $2^{31} - 1$ . Read lines until end of file.

Output

For each input line, print one line containing the first number, a hyphen, and the compressed form of the second number.

Examples4

Example 1

Input

10-18
83294-84137
100-200

Expected output

10-8
83294-137
100-00

Example 2

Input

123-283
4137-4223
8543-8613

Expected output

123-283
4137-23
8543-13

Example 3
Input
```
2839-2906
2839-3006
```
Expected output
```
2839-06
2839-006
```
Example 4
Input
```
0-5
5-15
1-12
```
Expected output
```
0-5
5-5
1-12
```