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 \leq n \leq 10^{9})$$$

Output

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

(Without the quotes)

Examples
Input
4
Output
Mahmoud
Input
3
Output
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.