Wizard of Odds

Interview

Time limit2sMemory limit512 MB

Summary

Given N possible secret numbers and K yes/no questions, decide whether K adaptive questions always identify the number, where K questions distinguish at most 2^K outcomes.

Level: Medium4 of 10
Topics: Math, Binary search, Bit manipulation, Implementation
Solved: No attempts yet

Problem

A long journey ends at the hall of the Wizard of Odds, who promises to grant any wish if you solve one puzzle.

The wizard first tells you two integers $N$ and $K$ . He then secretly picks an integer from 1 to $N$ inclusive and keeps it to himself.

Your goal is to name that secret number correctly. Before naming it you may ask $K$ questions that the wizard answers with true or false, for example "is the number even", "is the number between 7 and 10", "is the number 17 or 22", or "is the number prime". The wizard always answers honestly. Once all $K$ answers are in you must name one number. Name it correctly and your wish is granted. Name it wrongly and you become a flying monkey.

Formally, a question is a function from $\{1, 2, \ldots, N\}$ to the two values true and false, and the wizard tells you the value of that function at his secret number. You may choose each question after seeing the answers to the earlier ones.

Given $N$ and $K$ , decide whether $K$ questions always pin down the secret number, no matter which number the wizard picked.

Input

The first line contains two integers $N$ and $K$ separated by a single space. ( $2 \le N \le 10^{101}$ , $0 \le K \le N$ )

Both values can exceed the range of a 64 bit integer.

Output

If you can guarantee a win, print Your wish is granted! on the first line. Otherwise print You will become a flying monkey!. Do not print the quotes.

Examples2

Example 1
Input
```
8 3
```
Expected output
```
Your wish is granted!
```

Example 2

Input

1234567890987654321 2

Expected output

You will become a flying monkey!