AT_arc148_b.[ARC148B] dp

对于仅由 d 和 p 组成、长度为 $L$ 的字符串 $T$，定义 $T$ 经过 $180$ 度旋转后的字符串为 $f(T)$。更严格地说，$f(T)$ 满足以下条件：

• $f(T)$ 是仅由 d 和 p 组成、长度为 $L$ 的字符串。
• 对于所有满足 $1 \leq i \leq L$ 的整数 $i$，$f(T)$ 的第 $i$ 个字符与 $T$ 的第 $L+1-i$ 个字符不同。

例如，当 $T = $ ddddd 时，$f(T) = $ ppppp；当 $T = $ dpdppp 时，$f(T) = $ dddpdp。

给定一个仅由 d 和 p 组成、长度为 $N$ 的字符串 $S$。
你可以进行 $0$ 次或 $1$ 次如下操作：

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

例如，$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|}$，$S$ 字典序小于 $T$，当且仅当满足以下两条之一。这里 $|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$ 的字符。

输入按以下格式从标准输入读入。

$N$ $S$

请输出答案。

限制条件

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

样例解释 1

选择 $(L, R) = (2, 5)$。$T = $ pdpp，$f(T) = $ ddpd，所以操作后的 $S$ 为 dddpdd。在所有可能得到的字符串中，dddpdd 字典序最小，因此输出它。

样例解释 2

有时不进行操作是最优的。

由 ChatGPT 4.1 翻译