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 翻译