Run-Length Encoding

The task is to implement Run-Length Encoding (RLE) for a given string. In this encoding, each maximal substring of repeated characters is replaced by the character followed by the number of times it occurs consecutively. Formally, if a character \( c \) appears \( k \) times in succession, it will be encoded as \( c^k \) (i.e. as the concatenation of \( c \) and \( k \)).

For example, the string "aaabbccccd" is encoded as "a3b2c4d1". Your program should take the input string from standard input and output its run-length encoding to standard output.

inputFormat

The input consists of a single line containing the string to be encoded. The string may contain letters and digits and can be empty.

outputFormat

Output the run-length encoded string as described in the problem.

aaabbccccd

a3b2c4d1