406412: GYM102397 F Weird Game

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!

the input contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^{9})$$$

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

(Without the quotes)

4

Mahmoud

3

Bashar

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.