## Goal

@@

( — )

(>___<)

^^'''^^

Avoid deadlocks:

Given are `n` stones as array. The middle stone s is unoccupied at the start. On each of the left (`n`-1)/2 stones sits a male m frog looking to the right; on each of the right (`n`-1)/2 stones is a female f frog looking to the left.

(m)> (m)> (m)> (m)> ... (m)> s <(f) ... <(f) <(f) <(f) <(f)

The frogs can only jump in the direction they are facing. If the corresponding neighboring stone is free, the frog can jump directly to this stone. It is also possible to jump over **one** neighboring frog in order to get to a corresponding free stone.

We are looking for a sequence of jumps such that all male frogs are on the right (n-1)/2 stones and all female frogs are on the left (n-1)/2 stones. if there is no frog, return the input.

Male and female start positions can also be reversed, in which case their end position is also reversed.

Schematic example:

n=3, m=f=1

(m s f) -> start with f and jump just to the left

(m f s) -> a new stone is free

(m f s) -> consider the next possible male frog(s) and jump to the free stone

(s f m) -> a new stone is free

(s f m) -> consider the next possible female fog(s) and jump to the free stone

(f s m) -> a new stone is free

(f s m) -> result

Output:

Return the state of the array on a separate line after each round.

e.g. Input:

m s f

Output:

m s f

s m f

f m s

f s m

**Be courteous and start with the ladies.**
Input

**Line 1:** A string with frog position

Output

**Line 1:** starting grid

**Line 2:** first move

..

**Last line:** final grid

Constraints

3 ≤ `n` ≤ 100

`n` is odd

number of m = number of f

Example

Output

m s f
m f s
s f m
f s m