Encryption of corruption schemes

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

The problems Encryption of corruption schemesand Decryption of corruption schemesare related to each other, but they can be solved independently. The next four paragraphs are identical in both problem statements.

There is one Tatar working in ZENyk’s office. Every month he comes up with a new brilliant corruption scheme and willingly shares it with Zenyk in a message. This month was not without a new sly scheme. However, the Tatar is not stupid. He knows that the message with the scheme for Zenyk can be intercepted by law enforcement. Therefore, he encrypts it with the run-length encoding algorithm.

Run-length encoding (RLE) is a simple data compression algorithm that operates on data runs, i.e., sequences in which the same character occurs several times in a row. During encoding, a string of identical characters making up a run is replaced by a string containing the repeated character itself and the number of its repetitions (From Wikipedia).

Let’s consider an example of encoding the string AAAABBBBBBBACBBBBDDDDDDDDDDD. If we apply the RLE algorithm to it, we get 4A7B1A1C4B11D. The latter notation is interpreted as four A, seven B, one A, one C, four B, eleven D.

Note that 4A4B3B1A1C4B7D4D is not a correctly encoded string — complete runs must be written down. 4A7BAC4B11D is also not a correctly encoded string — even if the length of a character run is equal to one, 1 must still be written down.

Encrypt the Tatar’s corruption scheme using the RLE algorithm.

Input

The input data contains a single string \(s\) — the Tatar’s corruption scheme.

Output

Output the corruption scheme encoded with the RLE algorithm.

The length of the encoded scheme will not exceed \(10^5\) characters.

Constraints

\(1 \le |s| \le 10^5\),

\(s\) consists of uppercase Latin letters.

Samples