题目内容

你是一名星际通讯员，接收到了一段经过特殊编码的波纹消息 $t$。原始消息 $s$ 仅由小写字母组成，而编码后的波纹消息 $t$ 由大小写字母混合表示。解码规则如下：从左向右依次处理 $t$ 中的每个字符；若遇到小写字母 $x$，则直接在解码结果的末尾追加一个 $x$；若遇到大写字母 $X$，则需要找出以该字符开头的、由相同大写字母构成的极大连续段，记该段的长度为 $k$，然后在解码结果的末尾追加 $2^k$ 次对应的小写字母 $x$，并整体跳过这段大写字母继续向后处理。给定波纹消息 $t$，请你输出原始消息 $s$。

数据范围：波纹消息 $t$ 的长度 $m$ 满足 $m \le 10^5$。

输入描述

第一行包含一个整数 $m$，表示波纹消息的长度。 第二行包含一个长度为 $m$ 的字符串 $t$，字符串仅由大小写字母组成。