22851번 - 흑왕과 어둠의 게임 대진표 인터랙티브

차마 이름을 말하기조차 힘든 26대 어둠의 왕, blackking26. 그는 매년 그의 추종자를 1명 선발한다. 그 방법은 바로 죽음의 가위바위보 토너먼트이다.

토너먼트에는 사전에 지정된 어둠의 선별 인원 2^N명이 참가하고, 각 선별 인원은 1부터 2^N까지 번호를 부여받는다. 선별 인원은 각자 "고유 모양"을 가지고 있어, 각 인원은 토너먼트 내내 그 모양만 낼 수 있다. 예를 들어 고유 모양이 주먹인 선별 인원은 모든 게임에서 주먹만 낸다.

토너먼트는 모든 선별 인원이 한 번씩 등장하는 길이 2^N의 대진표로 표현된다. 토너먼트는 총 N개의 라운드로 이루어져 있다. 첫 번째 라운드에서는 대진표 상에서 2i-1번째에 위치한 선별 인원과 2i번째에 위치한 선별 인원이 경기를 진행하며(1 ≤ i ≤ 2^N-1), 이후 T번째(T ≥ 2) 라운드에서는 이전 라운드의 2i-1번째 경기의 승자와 2i번째 경기의 승자가 경기를 진행한다(1 ≤ i ≤ 2^N-T ). 토너먼트의 모든 경기는 평범한 가위바위보의 규칙에 따라 승패를 결정하며, 비겼을 경우 대진표 상 좌측에 있는 선별 인원이 승리한다. 한 번이라도 패배한 사람은 끝 없는 절망과 고통을 맛보게 된다. 

blackking26은 K번 선별 인원이 마음에 들었다. 그의 아끼는 추종자 리나에게 K번 선별 인원이 우승하는 대진표를 짜라고 명령하였다.

당신은 리나의 조수로서 리나에게 그러한 대진표를 짤 수 있는지 알려주려고 한다. 당신은 어둠의 대진표라는 도구를 사용할 수 있다. 어둠의 대진표에 번호 4개를 입력하면, 그 번호를 가진 선별 인원 4명이 순서대로 1, 2, 3, 4번째 자리에 위치하는 길이 4의 대진표로 토너먼트를 할 경우의 결과를 알려준다. 특별히 어둠의 대진표는 3위 결정전도 진행하여 4명 모두의 순위를 알려준다. 어둠의 대진표를 사용해서 정말로 토너먼트가 개최되는 건 아니므로, 어둠의 대진표의 실행 결과는 다른 어둠의 대진표의 결과나 실제 토너먼트의 결과에 영향을 주지 않는다. 하지만 어둠의 대진표는 굉장히 위험하기 때문에 사용 횟수에 제한이 있다.

만약 조건을 만족하는 대진표를 짤 수 없다면 blackking26은 크게 분노하여 리나를 죽일 것이다... 사실 당신이 진정으로 알려주어야 할 것은 리나가 살 수 있는지에 대한 여부이다. 어둠의 대진표를 잘 활용하여 이를 알아내보도록 하자. 

첫 줄에 수 N과, blackking26이 마음에 든 선별 인원의 번호 K가 주어진다.

당신이 작성한 프로그램은 채점 프로그램과 아래와 같이 상호작용해야 한다.

• 먼저 당신의 프로그램은 입력으로 N과 K를 입력받는다.
• 어둠의 대진표를 사용하려면 ? A B C D와 같은 줄을 출력한다. A, B, C, D는 선별 인원의 번호를 뜻하며 1이상 2^N이하의 서로 다른 정수이어야 한다.
• 당신의 프로그램이 위와 같이 출력할 때마다, 채점 프로그램은 토너먼트 결과를 제공한다. 1등의 번호, 2등의 번호, 3등의 번호, 4등의 번호를 공백으로 구분하여 4개의 정수로 제공하며, 당신은 4개의 정수를 입력받음으로써 이 정보를 얻을 수 있다.
• 만약 리나가 살 수 있다면 ! Y를, 살 수 없다면 ! N을 출력해 종료한다.
• 각 줄을 출력한 뒤에는 출력 버퍼를 비워야 한다. (노트 문단 참조)

• 2 ≤ N ≤ 16
• 1 ≤ K ≤ 2^N
• 어둠의 대진표를 사용하는 횟수는 44,444회 이하여야 한다. 

출력 버퍼를 비우는 방법은 아래와 같다.

• C의 경우: fflush(stdout);
• C++의 경우 : std::cout.flush();
• python의 경우: sys.stdout.flush()
• 기타 언어의 경우: 각 언어의 documentation을 참조하라.