Run-Length Decoding

Given a string s, consisting of digits and lowercase alphabet characters, that’s a run-length encoded string, return its decoded version.

Note: The original string is guaranteed not to have numbers in it.

Constraints

• 0 ≤ n ≤ 100,000 where n is the length of s

https://binarysearch.com/problems/Run-Length-Decoding

Examples

Example 1

Input

• s = 4a3b2c1d2a

Output

• answer = aaaabbbccdaa

Solution