Дешифрування корупційних схем

Обмеження: 2 сек., 256 МіБ

Задачі «Шифрування корупційних схем» і «Дешифрування корупційних схем» є пов’язаними між собою, але їх можна розв’язувати окремо одну від одної. Наступні чотири абзаци є однаковими в обох умовах.

В офісі ЗЕника працює один татарин. Щомісяця він придумує нову геніальну корупційну схему й охоче ділиться нею із Зеником у повідомленні. Цього місяця знову не обійшлося без нової хитрої схеми. Однак Татарин — не дурний. Він знає, що повідомлення зі схемою для Зеника можуть перехопити правоохоронці. Тому він шифрує його алгоритмом кодування довжин серій.

Кодування довжин серій (англ. Run-length encoding, RLE) — простий алгоритм стиснення даних, який оперує серіями даних, тобто послідовностями, у яких один і той ж символ зустрічається кілька разів поспіль. При кодуванні рядок однакових символів, що становлять серію, замінюють рядком, який містить сам повторюваний символ і кількість його повторів (З Вікіпедії).

Розгляньмо приклад кодування рядка AAAABBBBBBBACBBBBDDDDDDDDDDD. Якщо застосувати алгоритм RLE до нього, то отримаємо 4A7B1A1C4B11D. Останній запис інтерпретується як чотири A, сім B, одна A, одна C, чотири B, одинадцять D.

Зверніть увагу, що 4A4B3B1A1C4B7D4D не є правильно закодованим рядком — треба записувати цілі серії. 4A7BAC4B11D також не є правильно закодованим рядком — навіть якщо довжина серії символа дорівнює одиниці, то все одно потрібно записувати 1.

Татарин уже надіслав Зеникові зашифровану схему. Зенику цікаво, наскільки далеко цього разу зайшла фантазія татарина, і він хоче чимшвидше декодувати повідомлення.

Дешифруйте корупційну схему.

Вхідні дані

Вхідні дані містять єдиний рядок \(s\) — закодовану алгоритмом RLE корупційну схему.

Вихідні дані

У єдиному рядку виведіть декодовану схему.

Довжина декодованої схеми не перевищуватиме \(10^5\) символів, і вона складатиметься тільки з великих латинських букв.

Обмеження

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

\(s\) є правильно закодованою корупційною схемою.

Приклади