Problem Statement

You are given a string $S$ composed only of the characters 'd' and 'p'. You may perform at most one operation on the string:

• Select a subinterval $[l, r]$ of the string and perform a $180^\circ$ rotation on that interval.

The rotation operation consists of two steps:

1. Reverse the characters within the interval: Swap $S_{l+i}$ and $S_{r-i}$ for all $i$ such that $l + i \leq r - i$ and $i \in \mathbb{N}$.
2. Invert the characters: Replace all 'd' characters with 'p' and all 'p' characters with 'd'.

Your goal is to perform at most one such operation (or no operation at all) to obtain the lexicographically smallest possible string.

Lexicographical order: This is the natural ordering of strings, comparing characters one by one from left to right.

Input

The first line contains an integer $n$, the length of the string $(1 \leq n \leq 5000)$.

The second line contains a string consisting only of characters 'd' and 'p'.

Output

Output a single string, representing the lexicographically smallest string that can be obtained by performing at most one operation.

Example

Input 1

6
dpdppd

Output 1

dddpdd

Input 2

3
ddd

Output 2

ddd

Input 3

11
ddpdpdppddp

Output 3

ddddpdpdddp

Explanation

• In Example 1, rotating the interval $[2,5]$ results in the lexicographically smallest string.
• If the original string is already in its smallest lexicographical form, you may choose to make no changes.

Constraints

• $1 \leq n \leq 5000$