F. Weird Game

F. Weird Game

time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Some day Bashar and Mahmoud felt hungry so they decided to play a game with food.

Ayoub made 𝑛$n$ cup cakes for Bashsar and Mahmoud.

So the game goes as follow, each player can do one of these actions alternatively :

1. eat 1 cup cake (so the number of cup cakes will be subtracted by 1). 
2. eat exactly half of the cup cakes (if the number of cup cakes is even number). 

If the number of cup cakes is equals to 1 the current player loses.

If Mahmoud starts, and each player played optimally, print the name of the winner!

Input

the input contains a single integer 𝑛$n$ (1≤𝑛≤109)$(1\le n\le {10}^9)$

Output

Print 'Mahmoud' if Mahmoud wins, print 'Bashar' otherwise.

(Without the quotes)

Examples

input

Copy

4

output

Copy

Mahmoud

input

Copy

3

output

Copy

Bashar

Note

In first sample:

In first step the number of cup cakes is 4 and it's Mahmoud turn, Mahmoud decided to eat one cup cake so the remaining cup cakes are 3.

Then Bashar can only eat one cup cake so the remaining cup cakes are 2.

Mahmoud eats one cup cake and the remaining is only 1 cup cake.

It's Bashar's turn and there is only one cup cake, so Bashar loses.