dp

时间限制：2s
空间限制：1024MB

题目描述

对于一个只由 d 和 p 组成的字符串 $T$，定义 $f(T)$ 为将 $T$ 旋转 $180$ 度后得到的字符串。具体地，先反转字符顺序，再把每个 d 变为 p、每个 p 变为 d。例如 $f($ddddd$)=$ppppp，$f($dpdppp$)=$dddpdp。

给定一个长度为 $N$、只由 d 和 p 组成的字符串 $S$。你可以执行零次或一次下列操作：

• 选择 $1\le L\le R\le N$，把 $S_LS_{L+1}\ldots S_R$ 替换为 $f(S_LS_{L+1}\ldots S_R)$。

求最终可能得到的字符串中字典序最小的一个。

输入格式

第一行输入整数 $N$，第二行输入字符串 $S$。

输出格式

输出字典序最小的可达字符串。

样例输入 1

6
dpdppd

样例输出 1

dddpdd

样例输入 2

3
ddd

样例输出 2

ddd

样例输入 3

11
ddpdpdppddp

样例输出 3

ddddpdpdddp

数据范围

对于所有数据，$1\le N\le5000$，$S$ 只含 d 和 p。