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

게임 "배관공 Mariusz"(Plumber Mariusz)는 $n + 1$개의 레벨(0부터 $n$까지 번호가 매겨짐)로 이루어져 있으며, 각 레벨은 $k$개의 버전(0부터 $k - 1$까지 번호가 매겨짐)을 가집니다. 마지막 레벨을 제외한 모든 레벨의 각 버전 끝에는 왼쪽과 오른쪽 두 개의 파이프가 있으며, Mariusz는 그중 하나로 뛰어들어야 합니다. 각 파이프에는 일정 개수의 동전이 들어 있고 다음 레벨의 버전 중 하나로 이어집니다. (레벨 0을 제외한) 각 레벨의 각 버전으로는 정확히 두 개의 파이프가 이어집니다; 이 두 파이프는 이전 레벨의 모든 $k$개 버전에서 나오는 $2 \cdot k$개의 파이프 중 임의의 두 개일 수 있습니다.

한 번의 플레이는 레벨 0의 버전을 하나 선택한 뒤 왼쪽 또는 오른쪽 파이프를 $n$번 선택하는 것으로 이루어지며, 플레이의 결과는 방문한 $n$개의 파이프에서 수집한 동전의 총개수입니다. 각 파이프에 동전이 몇 개 있었는지나 각 레벨의 어떤 버전을 방문했는지는 알 수 없습니다. 파이프 안의 동전은 항상 초기 값으로 재설정되므로 모든 플레이는 독립적입니다. 따라서 한 번의 플레이는 다음 함수로 나타낼 수 있습니다:

int rozgrywka(int ver, string s), 여기서 $\text{ver} \in [0, k - 1]$이고 $s$는 $n$개의 문자 L과 P로 이루어진 문자열입니다.

참고로 L과 P는 각각 폴란드어로 왼쪽과 오른쪽을 뜻하는 단어에 해당합니다.

최대 $300\,000$번의 테스트 플레이를 수행하고 그 결과를 알아낼 수 있습니다. 그 후 플레이에 관한 질의를 최대 $10\,000$개 받게 됩니다. 여러분의 과제는 그 결과를 구하는 것입니다.

각 테스트는 상호작용이 시작되기 전에 고정되어 있습니다(즉, 인터랙터는 적응형이 아닙니다). 하나의 테스트는 $n + 1$개의 층(레벨)으로 배열된 $(n + 1) \cdot k$개의 정점을 가진 방향 가중치 그래프와 $q$개의 질의 $(\text{ver}, s)$를 포함합니다. 마지막 층을 제외한 각 정점은 두 개의 나가는 간선(왼쪽과 오른쪽)을 가지며, 각 간선은 동전 개수 $c \in [1, 10^8]$와 이어지는 버전 $v \in [0, k - 1]$로 설명됩니다. 층 0에 있는 정점을 제외한 모든 정점의 진입 차수가 정확히 2임을 기억하세요.

버퍼 비우기

각 줄을 출력한 후에는 반드시 출력 버퍼를 비워서(flush) 인터랙터가 출력 줄을 받을 수 있도록 해야 합니다. 예를 들어, C++에서는 cout << "!" << endl; 또는 printf("!\n"); fflush(stdout);를 사용하여 느낌표가 포함된 줄을 출력할 수 있습니다. Python에서는 print("!", flush=True)를 사용할 수 있습니다. 각 줄 뒤에 버퍼를 비우지 않고 여러 줄을 출력하거나, 인터랙터의 응답을 읽지 않고 많은 줄을 출력하는 경우 인터랙터의 안정적인 동작을 보장하지 않습니다. 프로그램은 어떠한 파일도 열어서는 안 됩니다.

상호작용 프로토콜

전체 통신 흐름은 아래와 같습니다:

• 첫 번째 줄에서 두 정수 $n$과 $k$ ($1 \le n, k \le 20$)를 읽습니다 — $n + 1$개의 레벨이 있으며, 각 레벨마다 $k$개의 버전이 있습니다.
• 최대 $300\,000$번 테스트 플레이를 수행합니다:
  • ? ver s 형태의 한 줄(따옴표 제외)을 출력합니다. 여기서 $\text{ver} \in [0, k - 1]$이고 $s$는 $n$개의 문자 L과 P로 이루어진 문자열입니다. 버퍼를 비웁니다.
  • 다음 줄에서 플레이 결과인 정수 $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$)를 읽습니다.
• 단일 문자 !(느낌표)가 포함된 한 줄을 출력합니다. 버퍼를 비웁니다.
• 다음 줄에서 질의의 개수를 나타내는 정수 $q$ ($1 \le q \le 10\,000$)를 읽습니다.
• $q$개의 질의 각각에 대해:
  • 다음 줄에서 정수 $\text{ver}$와 문자열 $s$(제한은 위와 동일)를 읽습니다.
  • 플레이 결과(정수)가 포함된 한 줄을 출력합니다. 버퍼를 비웁니다.

위 그림은 첫 번째 예제 테스트 ($n = 2; k = 4$)를 보여 줍니다. 두 개의 최종 질의가 점선으로 표시되어 있습니다: rozgrywka(0, "LL") $= 20 + 3 = 23$ 및 rozgrywka(1, "PL") $= 9 + 10 = 19$.

예제

다음은 통신 흐름의 예시입니다:

노트

첨부 파일(QOJ의 "attachment" 탭에서 다운로드 가능)에는 통신은 올바르게 수행하지만 결과를 잘못 계산하는 예제(오답) 풀이 G.cpp와 G.py가 들어 있습니다. 또한 디렉터리에는 예제 체커 Gsoc.cpp와 예제 테스트(G0a.in, G0b.in, G0c.in, 그리고 $n = k = 20$인 큰 랜덤 테스트 G0d.in)가 포함되어 있습니다. 테스트 파일의 형식은 Gsoc.cpp 시작 부분의 주석에 설명되어 있습니다.

예제 체커 Gsoc.cpp는 QOJ에서 사용되는 체커와 다릅니다. 입력이나 플레이 함수의 인자를 검증하지 않을 수 있습니다.

스크립트 run.sh를 사용하여 풀이를 실행할 수 있습니다. 이 명령은 컴파일된 프로그램과 테스트 파일 이름을 인자로 받습니다. 예를 들어, 예제 테스트 G0a.in에서 예제 프로그램을 실행하려면 다음과 같이 합니다:

• C++: g++ G.cpp -o G.e && ./run.sh "./G.e" G0a.in
• Python: ./run.sh "python3 G.py" G0a.in