시간 제한메모리 제한제출정답맞은 사람정답 비율
6 초 1024 MB5710713.208%

문제

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

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

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

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

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

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

입력

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

출력

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

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

제한

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

예제 입력 1

2 3

3 2 1 4

예제 출력 1

​
? 1 3 2 4

! Y

빈 줄은 실제로 출력하는 것이 아닌, 문제의 상호작용 관련하여 직관적으로 참가자의 이해를 돕기 위함입니다. 어떤 경우에도 빈 줄을 출력하거나, 빈 줄을 입력받으려고 해서는 안 됩니다.

예제 입력 2

2 3

4 1 2 3

4 2 1 3

1 3 4 2

예제 출력 2

​
? 3 1 2 4

? 3 2 4 1

? 1 2 3 4

! N

1 2 3 4번 선별인원의 고유 모양은 각각 보자기, 보자기, 주먹, 가위로, 어떻게 대진표를 짜도 3번 선별인원이 우승하는 것은 불가능하다. 

빈 줄은 실제로 출력하는 것이 아닌, 문제의 상호작용 관련하여 직관적으로 참가자의 이해를 돕기 위함입니다. 어떤 경우에도 빈 줄을 출력하거나, 빈 줄을 입력받으려고 해서는 안 됩니다.

노트

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

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

출처

Contest > Semi-Game Cup > Semi-Game Cup 2 F번

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.