题目描述

给定一个仅由字符 'd' 和 'p' 组成的字符串 $S$。你可以对字符串进行最多一次操作：

• 选择字符串的某个子区间 $[l, r]$，对该区间进行 $180^\circ$ 翻转。

翻转操作包括以下两个步骤：

1. 区间内字符反转：交换 $S_{l+i}$ 和 $S_{r-i}$，其中 $l + i \leq r - i$ 且 $i \in N$。
2. 字符互换：将字符 'd' 替换为 'p'，将字符 'p' 替换为 'd'。

你需要通过进行一次这样的操作（或者不进行任何操作），使得最终得到的字符串字典序最小。

字典序：字典序是字符串的自然排列顺序，首先比较首字母，若首字母相同，则比较第二个字母，以此类推。

输入格式

第一行一个整数 $n$ 表示字符串的长度 $(1 \leq n \leq 5000)$。

第二行一个只包含字符 'd' 和 'p' 的字符串。

输出格式

输出一个字符串，表示通过最多一次操作后得到的字典序最小的字符串。

样例 #1

样例输入 #1

6
dpdppd

样例输出 #1

dddpdd

样例 #2

样例输入 #2

3
ddd

样例输出 #2

ddd

样例 #3

样例输入 #3

11
ddpdpdppddp

样例输出 #3

ddddpdpdddp

提示

• 在样例 1 中，翻转区间 $[2,5]$ 后，得到的字符串是字典序最小的。
• 如果字符串本身已经是字典序最小的形式，可以不进行任何操作。