확률의 마법사

1부터 N까지의 비밀 수를 K번의 참/거짓 질문으로 항상 알아낼 수 있는지 판정한다. K번의 질문으로 구분 가능한 경우는 많아야 2^K가지다.

보통4수학이분 탐색비트 연산구현면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

긴 여행 끝에 확률의 마법사를 만났다. 마법사는 다음 퍼즐을 풀면 소원을 하나 들어주겠다고 약속한다.

마법사는 먼저 두 정수 NNKK를 알려준다. 그다음 1 이상 NN 이하의 정수를 하나 몰래 고르고, 그 값은 알려주지 않는다.

목표는 이 비밀 숫자를 정확히 맞히는 것이다. 답을 말하기 전에 그 숫자를 두고 참 또는 거짓으로 답이 돌아오는 질문을 KK번 할 수 있다. 예를 들어 "그 숫자는 짝수입니까", "그 숫자는 7 이상 10 이하입니까", "그 숫자는 17 또는 22입니까", "그 숫자는 소수입니까" 같은 질문이다. 마법사는 언제나 정직하게 참이나 거짓으로 답한다. 질문 KK개에 모두 답을 받은 뒤에는 숫자를 하나 말해야 한다. 맞히면 소원이 이루어지고, 틀리면 날개 달린 원숭이가 된다.

형식적으로 질문은 집합 {1,2,,N}\{1, 2, \ldots, N\}에서 참과 거짓 두 값으로 가는 함수이고, 마법사는 자신이 고른 비밀 숫자에서 이 함수가 어떤 값인지 알려준다. 앞선 질문의 답을 본 뒤에 다음 질문을 정해도 된다.

NNKK가 주어질 때, 마법사가 어떤 숫자를 고르더라도 질문 KK개만으로 비밀 숫자를 항상 알아낼 수 있는지 판정하라.

입력

첫째 줄에 두 정수 NNKK가 공백 하나로 구분되어 주어진다. (2N101012 \le N \le 10^{101}, 0KN0 \le K \le N)

두 값 모두 64비트 정수 범위를 넘을 수 있다.

출력

항상 이기는 것을 보장할 수 있으면 첫째 줄에 Your wish is granted!를 출력한다. 그렇지 않으면 You will become a flying monkey!를 출력한다. 따옴표는 출력하지 않는다.