题目内容

给定一个长度为 $n$ 的序列，每个位置上的符号有两种极性：阳态（用大写英文字母表示）和阴态（用小写英文字母表示）。

你需要按下标从小到大的顺序，依次处理每个位置 $i$（$1 \le i \le n$）。初始时，有一个跃迁步长 $d = 1$。对于当前处理的位置 $i$：

• 若 $i + d \le n$ 且序列的第 $i + d$ 个位置当前处于阳态（大写字母），则执行以下操作：先将该位置调整为阴态（改为小写字母），然后将步长 $d$ 的值增加 $1$；同时，若当前位置 $i$ 处于阴态（小写字母），则将其调整为阳态（改为大写字母）。
• 若上述条件不满足，则本次不对序列做任何修改，直接处理下一个位置。

请输出全部操作结束后的序列。

序列的长度 $n$ 满足 $1 \le n \le 2 imes 10^5$。序列中的字符仅由大写和小写英文字母组成。

输入描述

第一行包含一个整数 $n$，表示序列的长度。 第二行包含一个长度为 $n$ 的字符串，由大写和小写英文字母组成，表示每个位置的初始极性（大写为阳态，小写为阴态）。

输出描述

输出一个长度为 $n$ 的字符串，表示所有操作完成后每个位置的最终极性（阳态用大写字母，阴态用小写字母）。

样例1

输入

1
A

输出

A

说明

序列长度 $n=1$，初始步长 $d=1$。处理 $i=1$ 时，$i+d=2$ 已超出序列范围，不满足操作条件，因此序列保持不变。最终结果仍为 A。

样例2

输入

4
aBcD

输出

ABcd

说明

初始步长 $d=1$，序列为 aBcD。

• 处理 $i=1$：$i+d=2$，第 $2$ 个位置 B 为阳态（大写字母），满足条件。将 B 调整为阴态 b，$d$ 增加到 $2$；同时当前第 $1$ 个位置 a 为阴态，调整为阳态 A。序列变为 AbcD。
• 处理 $i=2$：当前 $d=2$，$i+d=4$，第 $4$ 个位置 D 为阳态，满足条件。将 D 调整为阴态 d，$d$ 增加到 $3$；当前第 $2$ 个位置 b 为阴态，调整为阳态 B。序列变为 ABcd。
• 处理 $i=3$ 与 $i=4$ 时，$d=3$，$i+d$ 均大于 $n$，不满足条件，无修改。 最终序列为 ABcd。

样例3

输入

5
abcDE

输出

abCdE

说明

初始步长 $d=1$，序列为 abcDE。

• 处理 $i=1$：$i+d=2$，第 $2$ 个位置 b 为阴态，不满足条件，无修改。
• 处理 $i=2$：$i+d=3$，第 $3$ 个位置 c 为阴态，不满足条件，无修改。
• 处理 $i=3$：$i+d=4$，第 $4$ 个位置 D 为阳态，满足条件。将 D 调整为阴态 d，$d$ 增加到 $2$；当前第 $3$ 个位置 c 为阴态，调整为阳态 C。序列变为 abCdE。
• 处理 $i=4$ 与 $i=5$ 时，$d=2$，$i+d$ 均大于 $n=5$，不满足条件，无修改。 最终序列为 abCdE。