보석 감정

설곽국에는 예지와 의행이라는 두 명품 브랜드가 있습니다. 두 브랜드에서는 보석을 꿰어 만든 명품 목걸이를 생산합니다. 각각의 보석은 영어 소문자 중 하나에 해당하는 약칭을 가지고 있습니다.

두 브랜드는 모두 보석을 자체 생산한다고 주장합니다. 브루는 두 브랜드의 보석이 비슷하다는 제보를 받고 목걸이의 보석을 비교해 보기로 했습니다. 보석은 육안으로는 비교가 불가능해서, 기계를 이용해 비교해야 합니다. 기계를 한 번 사용할 때마다 두 보석이 같은지 또는 다른지를 알 수 있습니다.

브루에게는 예지 브랜드에서 생산한 목걸이 A와, 의행 브랜드에서 생산한 목걸이 B가 있습니다. 두 목걸이에는 각각 $N$개의 보석이 있습니다. 기계를 적은 횟수로 사용해 목걸이 A와 목걸이 B 양쪽에 모두 포함된 보석 종류가 하나라도 있는지 판별하는 프로그램을 작성하세요.

입력의 첫 줄에는 목걸이 당 보석의 수 $N$과 서브태스크의 번호 $s$가 띄어쓰기를 사이에 두고 주어집니다. 이 두 수를 먼저 입력받아야 합니다.

이후 문자열 "? [X1] [Y1] [X2] [Y2]"를 출력해 기계를 이용할 수 있습니다. 각 칸에는 다음 규칙을 따라 출력합니다.

• [X1]: 첫 번째 보석이 속한 목걸이의 이름. 'A' 또는 'B'여야 합니다. (따옴표 제외)
• [Y1]: 첫 번째 보석이 해당 목걸이에서 몇 번째 보석인지를 출력합니다.
• [X2]: 두 번째 보석이 속한 목걸이의 이름. 'A' 또는 'B'여야 합니다. (따옴표 제외)
• [Y2]: 두 번째 보석이 해당 목걸이에서 몇 번째 보석인지를 출력합니다.

예를 들어, 목걸이 A의 세 번째 보석과 목걸이 B의 5번째 보석을 비교하는 경우, “? A 3 B 5”를 출력합니다.

출력한 뒤에는 줄을 바꾸고 표준 출력 버퍼를 플러시(flush)해야 합니다. 언어별로 표준 출력 버퍼를 플러시하는 방법은 다음과 같습니다.

• C++

  • fflush(stdout); (printf를 사용 중인 경우)
  • std::cout << std::flush; (std::cout을 사용 중인 경우)

• Python: sys.stdout.flush() (코드 최상단에 import sys가 필요)

기계를 한 번 사용한 뒤에는 정수 하나를 입력받아야 합니다. 해당 정수가 1인 경우 두 보석의 종류가 같고, 0인 경우 두 보석의 종류가 다름을 의미합니다.

만약 답을 알아낸 경우, 다음 지시에 따라 행동하세요.

• 두 목걸이에 같은 종류의 보석이 하나라도 있는 경우, "! 1"을 출력합니다.
• 두 목걸이에 같은 종류의 보석이 하나도 없는 경우, "! 0"을 출력합니다.

답을 출력한 이후 프로그램은 즉시 종료되어야 합니다.

• $N \le 1000$
• $1 \le s \le 2$
• 기계를 사용할 때, $\\{X\_1, X\_2\\} \subset \in \\{A, B\\}$이고, $1 \le Y\_1, Y\_2 \le N$을 만족해야 합니다.
• 모든 보석의 종류는 알파벳 소문자에 대응됩니다. 즉, 보석의 종류는 26가지 이하입니다.
• 채점 프로그램은 적응적이지 않습니다. 사전에 모든 목걸이 보석의 정보가 결정되어 있습니다.