34343번 - 카드 게임 인터랙티브

문제

이 문제는 인터랙티브 문제이다.

$L$ 이상 $R$ 이하인 서로 다른 정수가 앞면에 하나씩 적힌 카드 $R-L+1$장이 있다. 카드의 뒷면에는 아무것도 적혀있지 않다. 앨리스와 밥은 이 카드로 게임을 한다. 이때 한 명은 공격 측, 다른 한 명은 수비 측을 맡는다.

• 수비: 먼저 수비 측은 각 카드의 뒷면을 파란색 또는 빨간색 중 하나로 칠한다. 색칠이 끝나면 모든 카드를 앞면이 보이게 펼쳐 놓는다. 공격 측은 각 카드가 어느 색으로 칠해져 있는지 알 수 없다.
• 공격: 공격 측은 놓인 카드 중 원하는 것을 몇 장 골라 뒤집어 칠해진 색깔을 확인한다. 이때 뒤집을 수 있는 카드는 최대 10장이다.

이후 공격 측이 뒤집은 카드들 중에서, 아래 두 조건을 모두 만족하는 서로 다른 세 장의 카드를 찾을 수 있다면 공격 측이 승리한다.

• 세 카드의 뒷면 색깔이 모두 같다.
• 세 카드의 앞면에 적힌 숫자를 각각 $x, y, z$라고 할 때, $x\oplus y\oplus z=0$을 만족한다. $\oplus$는 Bitwise XOR 연산자이다.

찾지 못했다면 수비 측이 승리한다.

밥은 앨리스에게 공격과 수비 중 원하는 역할을 선택할 기회를 주었다. 이때 앨리스가 이길 수 있는 전략을 구현해보자. 그런 전략이 항상 존재함을 보일 수 있다.

인터랙션

첫째 줄에 두 양의 정수 $L,ドル $R$이 공백으로 구분되어 주어진다. $(1\le L\le R\le 200\ 000)$

이후 앨리스가 공격 역할을 고른다면 $\tt{attack},ドル 수비 역할을 고른다면 $\tt{defense}$를 출력한다.

$\tt{attack}$을 출력하였다면 밥이 카드의 뒷면에 색칠을 한다. 이후 다음의 쿼리를 최대 10번까지 할 수 있다.

• $\tt{?}$ $x$ : 앞면에 $x$가 적힌 카드를 뒤집어 본 후, 뒷면의 색깔을 입력받는다. 파란색인 경우 $\tt{B},ドル 빨간색인 경우 $\tt{R}$로 표현된다. $(L\le x\le R)$

승리 조건을 만족하는 서로 다른 세 카드를 찾았다면 다음을 출력해 답을 제출할 수 있다.

• $\tt{!}$ $x$ $y$ $z$ : 앞면에 각각 $x, y, z$가 적힌 세 카드가 승리 조건을 만족한다. $(L\le x, y, z\le R)$

$\tt{defense}$를 출력하였다면 길이가 $R-L+1$이고 $\tt{R},ドル $\tt{B}$로만 이루어진 문자열을 출력한다. $i$번째 문자는 앞면에 $L+i-1$가 적혀있는 카드의 뒷면에 색칠할 색깔을 나타낸다. 이때 출력된 색 배치는 공격 측이 카드를 어떻게 뒤집더라도 절대 승리할 수 없어야 한다.

각 줄을 출력 후 표준 출력 버퍼를 flush 해줘야 한다. 언어 별로 표준 출력 버퍼를 flush 하는 방법은 다음과 같다. 기타 언어의 경우 각 언어의 documentation을 참조하라.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()

이 문제의 인터랙터는 적응적이다. 단, 이전까지의 답변들과 모순되는 답변은 하지 않는다.

입력

출력

제한

노트

예제의 입출력은 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 개행 간격 등을 조절한 것으로, 실제 입출력과는 다르다.