题目描述

本题题解已发表至 讨论区

对于一个由 d 和 p 组成、长度为 $L$ 的字符串 $T$，定义 $f(T)$ 为将 $T$ 旋转 $180^\circ$ 后得到的字符串。更正式地说，$f(T)$ 满足以下条件：

• $f(T)$ 是一个由 d 和 p 组成、长度为 $L$ 的字符串；

• 对于所有满足 $1 \leq i \leq L$ 的整数 $i$，$f(T)$ 的第 $i$ 个字符与 $T$ 的第 $(L + 1 - i)$ 个字符不同。

例如，当 $T = \text{`ddddd`}$ 时，$f(T) = \text{`ppppp`}$；当 $T = \text{`dpdppp`}$ 时，$f(T) = \text{`dddpdp`}$。

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

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

例如，当 $S = \text{`dpdpp`}$ 且 $(L, R) = (2, 4)$ 时，$T = \text{`pdp`}$，$f(T) = \text{`dpd`}$，此时 $S$ 变为 $\text{`ddpdp`}$。

你的任务是输出 $S$ 可能得到的字典序最小的字符串。

什么是字典序？

一个字符串 $S = S_1S_2\ldots S_{|S|}$ 被称为字典序小于另一个字符串 $T = T_1T_2\ldots T_{|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$ 是一个长度为 $N$ 且仅由字符 `d` 和 `p` 组成的字符串。

$N$ 是一个整数。

输出描述

输出能够得到的字典序最小的字符串。

示例 1

输入

6
dpdppd

输出

dddpdd

说明

设 $(L, R) = (2, 5)$。此时有 $T = \text{`pdpp`}$ 且 $f(T) = \text{`ddpd`}$，因此 $S$ 变为 $\text{`dddpdd`}$。

这是可以得到的字典序最小的字符串，因此输出它。

示例 2

输入

3
ddd

输出

ddd

说明

不进行任何操作即是字典序最小的字符串。

示例 3

输入

11
ddpdpdppddp

输出

ddddpdpdddp