Description

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

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

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

给定一个仅由 d 和 p 组成、长度为 $N$ 的字符串 $S$。

你可以进行**$0$ 次或 $1$ 次**如下操作：

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

请输出所有可能得到的字符串中字典序最小的一个。

Format

Input

第一行包含一个整数 $N(1 \le N \le 5000)$。

第二行包含一个长度为 $N$、仅由 d 和 p 组成的字符串 $S$。

Output

输出一个字符串，表示答案。

Samples

6
dpdppd

dddpdd

2
dd

dd

11
ddpdpdppddp

ddddpdpdddp