408729: GYM103274 G Game of Baker

Baker invited his friend Amy to get somes snacks at a local shop. But Baker was secretly hoping to get some free snacks from her. He proposed making a game out of eating the snacks, where the loser pays the bill for the snacks.

For each game, the cats will select $$$N$$$ snacks and place them in a pile. Then they will take turns selecting a number of snacks to eat from the pile. Amy will always go first. Each turn consists of the following steps:

1. The active cat chooses a number $$$X$$$ between $$$1$$$ and $$$M$$$ (inclusive). They won't try to eat more snacks that are currently left in the pile.
2. The active cat will eat the chosen X number of snacks from the pile.
3. If the current cat ends up eating all the snacks left in the pile, meaning the pile is empty after they eat, the active cat wins the game.
4. On the other side, if the number of snacks remaining in the pile (counted in binary) contains an odd number of ones, then the active cat loses the game.

Assuming both cats play optimally, can you help figure out whether Baker will get "Free snacks!" or whether he will have to "Pay the bill" for each game.

The input consists of a single line, which contains $$$2$$$ integer numbers $$$N$$$ and $$$M$$$ where $$$1 \leq N \leq 5*10^8$$$ and $$$M$$$ $$$1 \leq M \leq 50$$$. $$$N$$$ will have an even number of ones in its binary representation.

Print a line with the text "Free snacks!" without quotes if Baker wins the game and "Pay the bil" if Amy wins instead.

3 1

Free snacks!

3 2

Free snacks!

3 3

Pay the bill