Đây là bài toán tương tác.

Trò chơi "Thợ sửa ống nước Mariusz" (Plumber Mariusz) gồm $n + 1$ màn chơi (được đánh số từ 0 đến $n$), mỗi màn có $k$ phiên bản (được đánh số từ 0 đến $k - 1$). Mỗi phiên bản của mọi màn (trừ màn cuối cùng) đều kết thúc bằng hai đường ống — ống bên trái và ống bên phải — và Mariusz phải nhảy vào một trong hai ống đó. Mỗi đường ống chứa một số lượng xu nhất định và dẫn đến một trong các phiên bản của màn tiếp theo. Có đúng hai đường ống dẫn đến mỗi phiên bản của mỗi màn (trừ màn không); đây có thể là hai đường ống bất kỳ trong số $2 \cdot k$ đường ống đi ra từ tất cả $k$ phiên bản của màn trước đó.

Một lượt chơi bao gồm việc chọn một phiên bản của màn không và sau đó chọn đường ống trái hoặc phải $n$ lần, và kết quả của lượt chơi là tổng số xu thu thập được trong $n$ đường ống đã đi qua. Chúng ta không biết có bao nhiêu xu trong mỗi đường ống hoặc những phiên bản nào của các màn đã được đi qua. Số xu trong các đường ống luôn được đặt lại về giá trị ban đầu, vì vậy tất cả các lượt chơi đều độc lập với nhau. Do đó, một lượt chơi có thể được biểu diễn bởi hàm:

int rozgrywka(int ver, string s), trong đó $\text{ver} \in [0, k - 1]$ và $s$ là một xâu gồm $n$ chữ cái L và P.

Lưu ý rằng L và P lần lượt tương ứng với các từ tiếng Ba Lan chỉ trái và phải.

Bạn có thể thực hiện tối đa $300\,000$ lượt chơi thử và biết được kết quả của chúng. Sau đó, bạn sẽ nhận được tối đa $10\,000$ truy vấn về các lượt chơi. Nhiệm vụ của bạn là xác định kết quả của chúng.

Mỗi test được cố định trước khi quá trình tương tác bắt đầu (tức là trình chấm không thích ứng). Một test chứa một đồ thị có hướng có trọng số với $(n + 1) \cdot k$ đỉnh được sắp xếp thành $n + 1$ tầng (màn), và $q$ truy vấn $(\text{ver}, s)$. Mỗi đỉnh (trừ các đỉnh ở tầng cuối cùng) có hai cạnh đi ra (trái và phải), mỗi cạnh được mô tả bởi số lượng xu $c \in [1, 10^8]$ và phiên bản $v \in [0, k - 1]$ mà nó dẫn tới. Nhắc lại rằng mọi đỉnh trừ các đỉnh ở tầng không đều có bậc vào đúng bằng 2.

Xả bộ đệm (Buffer flushing)

Sau khi in ra mỗi dòng, bạn phải xả bộ đệm đầu ra (flush) để trình tương tác nhận được dòng vừa in. Ví dụ, trong C++ bạn có thể in ra một dòng chứa dấu chấm than bằng cout << "!" << endl; hoặc dùng printf("!\n"); fflush(stdout);. Trong Python bạn có thể dùng print("!", flush=True). Chúng tôi không đảm bảo hành vi ổn định của trình tương tác nếu bạn in ra nhiều dòng mà không flush sau mỗi dòng, hoặc nếu bạn in ra nhiều dòng mà không đọc phản hồi của trình tương tác. Chương trình của bạn không được mở bất kỳ tệp nào.

Giao thức tương tác

Toàn bộ luồng giao tiếp được mô tả dưới đây:

• Đọc dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 \le n, k \le 20$) — có $n + 1$ màn, mỗi màn có $k$ phiên bản.
• Tối đa $300\,000$ lần, thực hiện một lượt chơi thử:
  • In ra một dòng có dạng ? ver s (không có dấu ngoặc kép), trong đó $\text{ver} \in [0, k - 1]$ và $s$ là một xâu gồm $n$ chữ cái L và P. Flush.
  • Đọc dòng tiếp theo chứa kết quả của lượt chơi — một số nguyên $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• In ra một dòng chứa một ký tự duy nhất ! (dấu chấm than). Flush.
• Đọc dòng tiếp theo chứa một số nguyên $q$ ($1 \le q \le 10\,000$) — số lượng truy vấn.
• Với mỗi truy vấn trong $q$ truy vấn:
  • Đọc dòng tiếp theo chứa một số nguyên $\text{ver}$ và một xâu $s$ (cùng giới hạn như trên).
  • In ra một dòng chứa kết quả của lượt chơi (một số nguyên). Flush.

Hình minh họa thể hiện test ví dụ đầu tiên ($n = 2; k = 4$). Hai truy vấn cuối cùng được đánh dấu bằng đường nét đứt: rozgrywka(0, "LL") $= 20 + 3 = 23$ và rozgrywka(1, "PL") $= 9 + 10 = 19$.

Ví dụ

Dưới đây là một ví dụ về luồng giao tiếp:

Ghi chú

Trong tệp đính kèm (bạn có thể tải xuống ở tab "attachment" trên QOJ), bạn sẽ tìm thấy các lời giải mẫu (không chính xác) G.cpp và G.py thực hiện giao tiếp đúng cách nhưng tính toán kết quả sai. Thư mục này cũng bao gồm: một trình chấm mẫu Gsoc.cpp và các test mẫu (G0a.in, G0b.in, G0c.in, cùng một test ngẫu nhiên lớn G0d.in với $n = k = 20$). Định dạng của các tệp test được mô tả trong phần chú thích ở đầu tệp Gsoc.cpp.

Trình chấm mẫu Gsoc.cpp khác với trình chấm được sử dụng trên QOJ. Nó có thể không kiểm tra tính hợp lệ của dữ liệu vào hoặc các đối số của hàm lượt chơi.

Bạn có thể chạy lời giải của mình bằng script run.sh. Câu lệnh nhận vào chương trình đã biên dịch và tên tệp test. Ví dụ, để chạy các chương trình mẫu trên test mẫu G0a.in:

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