Score : $500$ points

Problem Statement

For a string $T$ of length $L$ consisting of d and p, let $f(T)$ be $T$ rotated $180$ degrees. More formally, let $f(T)$ be the string that satisfies the following conditions.

• $f(T)$ is a string of length $L$ consisting of d and p.
• For every integer $i$ such that $1 \leq i \leq L$, the $i$-th character of $f(T)$ differs from the $(L + 1 - i)$-th character of $T$.

For instance, if $T =$ ddddd, $f(T) =$ ppppp; if $T =$ dpdppp, $f(T)=$ dddpdp.

You are given a string $S$ of length $N$ consisting of d and p. You may perform the following operation zero or one time.

• Choose a pair of integers $(L, R)$ such that $1 \leq L \leq R \leq N$, and let $T$ be the substring formed by the $L$-th through $R$-th characters of $S$. Then, replace the $L$-th through $R$-th characters of $S$ with $f(T)$.

For instance, if $S=$ dpdpp and $(L,R)=(2,4)$, we have $T=$ pdp and $f(T)=$ dpd, so $S$ becomes ddpdp.

Print the lexicographically smallest string that $S$ can become.

Constraints

• $1 \leq N \leq 5000$
• $S$ is a string of length $N$ consisting of d and p.
• $N$ is an integer.

Input

The input is given from Standard Input in the following format:

$N$

$S$

Output

Print the answer.

6
dpdppd

dddpdd

Let $(L, R) = (2, 5)$. Then, we have $T =$ pdpp and $f(T) =$ ddpd, so $S$ becomes dddpdd. This is the lexicographically smallest string that can be obtained, so print it.

3
ddd

ddd

It may be optimal to skip the operation.

11
ddpdpdppddp

ddddpdpdddp