解题思路

• 题意还原 给定压缩串 t（长度为 m，包含大小写字母）。从左到右处理：

  • 若当前字符是小写字母 x，在结果串 s 末尾追加一次 x；
  • 若当前字符是某个大写字母 X，设它所在的极大连续段长度为 k，则在结果串末尾追加 2^k 次对应的小写字母 x，随后整体跳过这段。 输出解压后的全小写字符串 s。

• 相关算法：线性扫描 + 分组（run-length）

题目内容

Tk 有一个长度为 $n$ 、仅由小写字母组成的字符串 $s$ 。为了便于携带，Tk 将字符串 $s$ 压缩为长度为 $m$ 、仅由大小写字母组成的字符串 $t$ 。解压缩满足如下规则(从左到右处理 $t$ )：

若当前字符为小写字母 $'x’$，则在还原串 $s$ 的末尾追加一次小写字母 $'x’$;

若当前字符为某个大写字母 $'X’$ ，设其所在的极大连续段为区间 $[l,r]$ (即 $t_l =···= t _r = 'X’$，且 $t_{l-1} ≠'X’、t_{r+1} ≠'X’$，越界时忽略)，令该段长度为 $k=r-l+1$ ，则在还原串 $s$ 的末尾追加 $2^k$ 次对应的小写字母 $'x’$，随后整体跳过这一段继续处理;

压缩前后不同字符出现的相对顺序保持不变。给定压缩后的字符串 $t$ ，请输出压缩前的字符串 $s$ 。

输入描述

在一行上输入长度为 $m$ 、仅由小写字母组成的字符串 $t$ 。

输出描述

在一行上输出长度为 $n$ 、仅由小写字母组成的字符串 $s$ 。

样例1

输入

5
aBBcD

输出

abbbbcdd