题目描述

对于一个由 'd' 和 'p' 组成的长度为 $L$ 的字符串 $T$，定义 $f(T)$ 为将 $T$ 逆时针旋转 $180$ 度得到的字符串。更准确地说，$f(T)$ 满足以下条件。

• $f(T)$ 是一个由 'd' 和 'p' 组成的长度为 $L$ 的字符串。
• 对于任意 $1 \leq i \leq L$，$f(T)$ 的第 $i$ 个字符与 $T$ 的第 $(L + 1 - i)$ 个字符不同。

例如，如果 $T =$ 'ddddd'，则 $f(T) =$ 'ppppp'；如果 $T =$ 'dpdppp'，则 $f(T) =$ 'dddpdp'。

给定一个由 'd' 和 'p' 组成的长度为 $N$ 的字符串 $S$。
你可以执行以下操作最多一次。

• 选择一对整数 $(L, R)$，满足 $1 \leq L \leq R \leq N$，令 $T$ 为 $S$ 中第 $L$ 到第 $R$ 个字符组成的子串。然后，用 $f(T)$ 替换 $S$ 中的第 $L$ 到第 $R$ 个字符。

例如，如果 $S =$ 'dpdpp'，且 $(L,R)=(2,4)$，则 $T =$ 'pdp'，$f(T) =$ 'dpd'，因此 $S$ 变为 'ddpdp'。

输出 $S$ 可能变为的字典序最小的字符串。

什么是字典序？

字符串 $S = S_1S_2\ldots S_{|S|}$ 被称为字典序较小于字符串 $T = T_1T_2\ldots T_{|T|}$，当且仅当以下 1 和 2 中的一个成立。其中，$|S|$ 和 $|T|$ 分别表示 $S$ 和 $T$ 的长度。

1. $|S| < |T|$ 且 $S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}$。
2. 存在一个整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$，满足以下两个条件：
   • $S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}$。
   • $S_i$ 在字母表顺序中小于 $T_i$。

约束条件

• $1 \leq N \leq 5000$
• $S$ 是一个由 'd' 和 'p' 组成的长度为 $N$ 的字符串。
• $N$ 是一个整数。

输入

从标准输入读取输入数据，输入格式如下：

$N$ $S$

输出

输出结果。

示例输入1

6
dpdppd

示例输出1

dddpdd

取 $(L, R) = (2, 5)$。则 $T =$ 'pdpp'，$f(T) =$ 'ddpd'，因此 $S$ 变为 'dddpdd'。
这是可以获得的字典序最小的字符串，因此输出它。

示例输入2

3
ddd

示例输出2

ddd

跳过操作可能是最优的选择。

示例输入3

11
ddpdpdppddp

示例输出3

ddddpdpdddp