Problem J. Improve RLE ≡

Author:I. Ludov, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  
Maximum points:100  

Statement

A computer programmer and mathematician Kumar Harikrishnan develops a new data compression system — ACM (Advanced Compression Method) — which will incorporate all of his brilliant ideas.

The first component of ACM will be a modification of well-known RLE algorithm, called Improved RLE. Since Kumar have much more difficult tasks to accomplish (such as to write Improved Hamming and Improved Lempel-Ziv), he asks you to implement this simple, yet important part of a system.

An algorithm should replace repeating substrings of source string with a single instance of substring concatenated with the number of repetitions. If some substring should not be repeated, it is concatenated with number 1.

Your program must find the shortest possible compression of the given string.

Input file format

A single line of input file contains the string to be compressed. It may contain spaces, but does not contain digits as Kumar has invented a complex digit-escaping system to prevent uncompressing ambiguity.

Output file format

Output file must contain minimal length compression of the source string. There should be no extra whitespace characters before or after the string.

Constraints

Length of the source string is from 1 to 1000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
aaaaaaaaaa
 
a10
2 
a c c c
 
a1 c3
3 
abc
 
abc1
0.027s 0.006s 15