Sweet Life

Interview

Time limit2sMemory limit1024 MB

Summary

Two players take up to k candies per turn, never the same count as the opponent's last move; find who wins from n candies with Masya moving first.

Level: Medium5 of 10
Topics: Game theory, Math
Solved: No attempts yet

Problem

The Fixiki eat energy, but they also love sweets. Today Papus, walking through Dim Dimych's apartment with Masya, found a box of candies on the table.

The box contains exactly $n$ candies. Both want to take as many as they can, but splitting them in half is too hard. So they invent a game.

Papus and Masya take turns removing candies from the pile. On each turn a player takes at most $k$ candies, because their hands are small. A player may not take the same number of candies that the opponent took on the previous turn, since repetition is boring.

The player who cannot move loses. Papus, a true gentleman, gave Masya the first move. The winner may divide the candies however they like. Tell them who wins under optimal play.

Input

The first and only line contains two integers $n$ and $k$ ( $1 \le n \le 10^9$ , $1 \le k \le 100$ ): the initial number of candies and the maximum number of candies that can be taken in one turn.

Output

Print <<Masya>> if Masya wins under optimal play, and <<Papus>> otherwise.

Examples2

Example 1
Input
```
4 2
```
Expected output
```
Masya
```
Example 2
Input
```
5 3
```
Expected output
```
Masya
```