Decryption of corruption schemes

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

The problems "Encryption of corruption schemes" and "Decryption of corruption schemes" are related to each other, but they can be solved independently of each other. The following four paragraphs are identical in both problem statements.

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

Run-length encoding (RLE) is a simple data compression algorithm that operates on runs of data, that is, sequences in which the same character occurs several times in a row. In encoding, a string of identical characters forming 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 record is interpreted as four A’s, seven B’s, one A, one C, four B’s, eleven D’s.

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

The Tatar has already sent the encrypted scheme to Zenik. Zenik is wondering how far the Tatar’s imagination went this time, and he wants to decode the message as quickly as possible.

Decrypt the corruption scheme.

Input

The input contains a single string \(s\) — the corruption scheme encoded with the RLE algorithm.

Output

In a single line, output the decoded scheme.

The length of the decoded scheme will not exceed \(10^5\) characters, and it will consist only of uppercase Latin letters.

Constraints

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

\(s\) is a correctly encoded corruption scheme.

Samples