A network layer compresses each packet payload using run-length counts: every maximal run of one repeated character becomes that character followed by the run's length (for example aabb becomes a2b2). To avoid ever making a payload bigger, the layer sends the compressed form only if it is strictly shorter than the original payload; otherwise it sends the original payload unchanged.

Given a payload of lowercase English letters, print whichever of the two the layer would send.

Input format

Line 1: a non-empty string of lowercase English letters.

Output format

A single line: the run-length compressed string if it is strictly shorter than the input, otherwise the original input string.

Constraints

• 1 <= length of the string <= 100000
• The string consists only of lowercase English letters (a-z).

aabcccccaaa

a2b1c5a3

abcdef

abcdef