Đây là bài toán giao tiếp với máy chấm (Interactive problem)

Jury có một con số ~n~ bí mật. Điều duy nhất bạn biết về con số này là ~1 \leq n \leq 2 \times 10^9~. Hãy đoán xem ~n~ là số nào trong không quá ~31~ câu hỏi.

Interaction

Mỗi lượt, bạn sẽ in ra một số x ~(1 \leq x \leq 2 \times 10^9)~ trên một dòng và đọc vào một chuỗi — phản hồi của máy chấm. Lưu ý hãy flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc std::endl trong ngôn ngữ lập trình C++ hoặc các câu lệnh tương ứng ở các ngôn ngữ lập trình khác.

Máy chấm sẽ phản hồi một trong ba chuỗi:

• BIGGER — nếu ~n > x~.
• SMALLER — nếu ~n < x~.
• HOLA — nếu ~n = x~. Chương trình của bạn phải kết thúc sau khi nhận được phản hồi này.

Sample Input 1

BIGGER
SMALLER
HOLA

Sample Output 1

1
9
5

Notes

Con số bí mật trong test này là ~5~.

• Truy vấn 1: ~1 < 5~, máy chấm trả về BIGGER.

• Truy vấn 9: ~9 > 5~, máy chấm trả về SMALLER.

• Truy vấn 5: ~5 = 5~, máy chấm trả về HOLA. Dừng chương trình.

Cho một mảng nguyên ~a[1..n]~ thỏa mãn:

• ~a[1]~ là giá trị nhỏ nhất của mảng,
• ~a[n]~ là giá trị lớn nhất của mảng,
• với mọi ~2 \le i \le n~, ta có ~|a[i] - a[i-1]| = 1~.

Bạn được cho thêm một tham số ~k~ và biết chắc rằng tồn tại ít nhất một vị trí ~id~ sao cho ~a[id] = k~. Nhiệm vụ của bạn là tìm ra một vị trí như vậy bằng cách thực hiện tối đa 16 lượt hỏi.

Input

Ban đầu, bạn cần đọc vào hai số nguyên ~n,~ ~k~ ~(1 \le n \le 10000)~ — kích thước mảng và giá trị cần tìm.

Interaction

Để thực hiện truy vấn, in ra một số nguyên id ~(1 \le id \le n)~ và đọc vào một chuỗi — phản hồi của máy chấm. Lưu ý hãy flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc std::endl trong ngôn ngữ lập trình C++ hoặc các câu lệnh tương ứng ở các ngôn ngữ lập trình khác.

Máy chấm sẽ phản hồi một trong ba chuỗi:

• BIGGER — tức là ~a[id] < k~.
• SMALLER — tức là ~a[id] > k~.
• HOLA — tức là ~a[id] = k~. Chương trình của bạn phải kết thúc sau khi nhận được phản hồi này.

Nếu bạn hỏi quá 16 lượt mà vẫn chưa nhận được HOLA, chương trình của bạn sẽ nhận được kết quả Wrong Answer.

Sample Input 1

BIGGER
SMALLER
HOLA

Sample Output 1

3
5
4

Notes

Giả sử mảng ẩn là ~[2,3,4,5,6,7]~ và ~k = 5~. Máy chấm in: ~6~ ~5~.

• Truy vấn 3: ~a[3] = 4 < 5~, máy chấm trả về BIGGER.

• Truy vấn 5: ~a[5] = 6 > 5~, máy chấm trả về SMALLER.

• Truy vấn 4: ~a[4] = 5 = k~, máy chấm trả về HOLA. Dừng chương trình.

Cô giáo nghĩ trong đầu một số nguyên dương ~X~ trong khoảng từ ~1~ đến ~10^6~. Các bạn học sinh cần tìm được số bí mật ~X~ với ít nhất các câu hỏi có dạng:

• Ước chung lớn nhất của số ~X~ với một số ~Y~ là bao nhiêu?

Bạn nào dùng càng ít câu hỏi thì điểm càng cao.

Hãy viết một chương trình, sử dụng các câu lệnh được cung cấp để tìm ra số bí mật ~X~ mà hết ít câu hỏi nhất.

Interaction

Để tương tác với máy chấm, hãy in mỗi lệnh trên từng dòng. Câu trả lời sẽ được máy chấm in ra trên một dòng khác, và bạn đọc vào. Lưu ý hãy flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc std::endl trong ngôn ngữ lập trình C++ hoặc các câu lệnh tương ứng ở các ngôn ngữ lập trình khác.

Bạn được phép sử dụng những câu lệnh sau:

• ucln Y với ~Y~ là một số nguyên dương bất kỳ (~1 \leq Y \leq 10^{18}~). Máy sẽ in ra ước chung lớn nhất của ~X~ và ~Y~.

• traloi x với ~x~ là một số nguyên dương bạn đã xác định được rằng đó là ~X~. Chương trình bắt buộc phải in ra traloi một lần duy nhất, nếu không sẽ bị ~0~ điểm. Thủ tục này khi được gọi sẽ tự động thoát chương trình bằng câu lệnh exit.

Scoring

Với mỗi bộ dữ liệu, nếu chương trình của bạn trả lời với đáp án không chính xác, chạy quá thời gian quy định, sử dụng quá ~1000000~ câu hỏi hoặc gặp các lỗi dẫn tới việc dừng chương trình, bài làm sẽ nhận ~0~ điểm cho bộ dữ liệu đó. Số điểm cho mỗi bộ dữ liệu sẽ giảm dần khi số câu hỏi bạn sử dụng tăng lên.

Cụ thể hơn, gọi ~P(Q)~ là số điểm nhận được nếu như đoán đúng sau ~Q~ câu hỏi. Số điểm sẽ được tính như nhau:

$$P(Q) = \begin{cases} 100 & \text{nếu } Q \leq 26000 \\ \left\lfloor 60 + 40 \times \left(\frac{27000-Q}{2000}\right) \right\rfloor & \text{nếu } 26000 < Q \leq 27000 \\ \left\lfloor 30 + 30 \times \left(\frac{80000-Q}{53000}\right) \right\rfloor & \text{nếu } 27000 < Q \leq 80000 \\ \left\lfloor 10 + 20 \times \left(\frac{100000-Q}{920000}\right) \right\rfloor & \text{nếu } 80000 < Q \leq 1000000 \\ 0 & \text{nếu } Q > 1000000 \end{cases}$$

Notes

Giả sử số bí mật là ~4~.

Ban đầu, Fran có một mảng rỗng ~a~. Fran thực hiện ~n~ truy vấn, mỗi truy vấn có dạng ~x~ — anh ta thêm ~x~ phần tử vào cuối mảng ~a~. Sau mỗi truy vấn, Fran muốn xác định phần tử nhỏ nhất trong mảng ~a~, và khi đã xác định được, anh ta sẽ loại bỏ phần tử đó khỏi mảng mà không làm thay đổi chỉ số của các phần tử còn lại.

Yêu cầu: Hãy xác định chỉ số của phần tử nhỏ nhất trong mảng sau mỗi truy vấn, bằng cách hỏi so sánh giữa các chỉ số.

Interaction

Đây là một bài toán tương tác. Nhiệm vụ của bạn là viết một chương trình tương tác để xử lý các truy vấn.

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 40~) — số lượng truy vấn.

Sau đó là ~n~ dòng, mỗi dòng chứa một số nguyên ~x_i~ (~1 \le x_i \le 2000~), biểu thị số phần tử được thêm vào mảng trong truy vấn thứ ~i~.

Sau mỗi truy vấn, bạn có thể gửi các câu hỏi dạng:

Với điều kiện ~i \neq j~, và cả hai chỉ số ~i, j~ phải là các chỉ số của phần tử hiện chưa bị loại bỏ. Trình chấm sẽ phản hồi:

• 0 nếu ~a_i < a_j~

• 1 nếu ~a_i > a_j~

Sau khi xác định được phần tử nhỏ nhất hiện tại, bạn phải in ra:

Trong đó ~x~ là chỉ số của phần tử nhỏ nhất hiện tại trong mảng ~a~ (chỉ số này chưa bị loại bỏ trước đó). Phần tử tại chỉ số ~x~ sẽ được loại bỏ ngay lập tức khỏi mảng.

Sau đó truy vấn tiếp theo sẽ bắt đầu. Sau truy vấn cuối cùng, chương trình kết thúc. Tổng số phần tử được thêm vào qua tất cả các truy vấn sẽ không vượt quá ~2000~.

Sample Input 1

3
3
1
0
0
1
1
1
0

Sample Output 1

? 1 2
? 1 3
? 2 3
! 2 1
? 1 4
! 4 1
? 1 5
! 1 1

Scoring

Chương trình của bạn sẽ được chấm điểm dựa trên tổng số câu hỏi bạn đã hỏi. Gọi ~q~ là tổng số câu hỏi, điểm được tính như sau:

• Nếu ~q \le 7000~: được 100 điểm

• Nếu ~7000 < q \le 20000~: được 30 điểm

• Nếu ~20000 < q \le 80000~: được 15 điểm

Notes

Giả sử mảng thực tế mà máy chấm giữ (ẩn với người chơi) là ~a = [3,2,4,1,5]~.

Quá trình tương tác có thể diễn ra như sau:

Đây là bài tương tác, hãy đọc hướng dẫn làm bài tương tác ở đây.

Cửa hàng VNOI gồm ~n~ món đồ, món đồ thứ ~i~ có giá ~p_i~. Các món đồ đều có giá đôi một phân biệt với nhau.

Bạn muốn mua toàn bộ các món đồ trong cửa hàng. Chủ cửa hàng nhận ra bạn là một khách VIP nên đưa cho bạn một voucher khuyến mãi như sau: bạn sẽ được miễn phí ~k~ món đồ, và phải trả tiền cho ~n- k~ món đồ còn lại. Tuy nhiên, điều thú vị ở đây là, bạn sẽ không biết giá trị của các món đồ, mà chỉ biết về các tham số ~n~ và ~k~ tương đương với số lượng món đồ và số món đồ được miễn phí.

Bạn muốn tối đa hóa lợi ích cho mình, nên muốn chọn các món đồ sao cho tổng số tiền các món đồ bạn phải trả là ít nhất có thể.

Tất nhiên, bạn sẽ được hỏi ông chủ những câu có dạng như sau, với mỗi lượt được quyền chọn hai số ~x~ và ~y~:

• ~?~ ~x~ ~y~ trong đó ~1\le x,y\le n~.
• Sau mỗi truy vấn bạn dùng ~endl~ để ngắt câu hỏi.
• Máy chấm sẽ đọc truy vấn và in về một số nguyên:
  • Nếu ~p[x] < p[y]~, in về y.
  • Ngược lại (khi ~p[x] > p[y]~), in về x.

Bạn không được trực tiếp đọc hay in giá trị của ~p[i]~ - chỉ so sánh thông qua các truy vấn trên.

Ở bài toán này, điểm số ở từng test của bạn sẽ được chấm bằng một hàm bí mật, chỉ biết rằng, gọi ~C_u~ là số thao tác mà bạn sử dụng, ~C_j~ là số thao tác mà giám khảo sử dụng:

• Nếu ~C_u \le C_j~ bạn sẽ được toàn bộ số điểm của test đó.
• Ngược lại, số điểm mà bạn nhận được sẽ được tính toán sao cho nếu ~C_u - C_j~ càng nhỏ, điểm số càng cao.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le n \le 10^3~, ~1 \le k \le n~) – số lượng món đồ và số món đồ được miễn phí.

• Sau khi đọc dòng này bạn sẽ bắt đầu quá trình tương tác.

Interaction

Để hỏi một truy vấn so sánh giá của hai món đồ ~x~ và ~y~, chương trình của bạn cần in "~?~ ~x~ ~y~" (với ~1 \le x, y \le n~).

Sau đó chương trình của bạn cần đọc kết quả do hệ thống cung cấp:

• Nếu ~p[x] < p[y]~, hệ thống trả về ~y~.
• Ngược lại (khi ~p[x] > p[y]~), hệ thống trả về ~x~.

Bạn không được dùng quá ~10^6~ truy vấn trong toàn bộ quá trình.

Để đưa ra đáp án, chương trình của bạn cần in "~!~ ~1~ ~1~", sau đó trên dòng tiếp theo in ra ~k~ số ~id_1, id_2, ..., id_k~ đôi một phân biệt là các món đồ mà bạn chọn để miễn phí. Việc đưa ra đáp án không tính vào số câu hỏi.

Sau khi in ra một truy vấn, bạn cần xuống dòng và flush output. Để làm điều này, hãy:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• flush(output) trong Pascal;
• stdout.flush() trong Python;

Example

Giả sử các món đồ có giá ẩn là ~p=[2,\,5,\,1,\,4,\,3]~, ~n=5~, và ~k=2~.

Trong ví dụ dưới đây, các truy vấn giúp xác định được món đồ ~2~ và ~4~ là hai món đồ có giá cao nhất để chọn miễn phí.

Sample Input

5 2

3

3

4

1

Sample Output

? 1 3

? 3 5

? 4 2

? 1 4

! 1 1
2 4

Lưu ý

• Mỗi truy vấn in đúng cú pháp ? x y rồi endl.
• Tổng số truy vấn không vượt quá ~10^6~.
• Khi hoàn thành, in ! 1 1 rồi dòng chứa đáp án.
• Đáp án bị coi là sai nếu dùng quá nhiều truy vấn hoặc in sai định dạng.

Trong bài toán này, có một số nguyên chưa biết ~x~ với ~1 \le x \le 10^9~. Nhiệm vụ của bạn là biến nó thành số nguyên ~n~ được cho trong input. Bằng cách sử dụng một CPU, bạn có thể gửi lệnh để thực hiện một trong các thao tác sau:

Trong đó, ~S(n)~ là hàm trả về tổng các chữ số của số nguyên không âm ~n~. Ví dụ: ~S(123) = 1 + 2 + 3 = 6~.

Bạn phải biến ~x~ thành ~n~ với càng ít thao tác càng tốt.

Input

Mỗi input gồm nhiều test case:

• Dòng đầu chứa số nguyên ~t~ (~1 \le t \le 100~) — số lượng test case.

• Mỗi test case gồm một dòng chứa một số nguyên ~n~ (~1 \le n \le 10^9~).

Interaction

Bạn có thể sử dụng không quá ~7~ lệnh với CPU để biến đổi từ ~x~ thành ~n~. Để gửi lệnh, bạn in ra một dòng theo đúng định dạng của một trong các lệnh sau:

• ~\texttt{add}~ ~y~: cộng số nguyên ~y~ (~-10^{18} \le y \le 10^{18}~) vào ~x~. Jury trả ~1~ nếu ~x + y~ nằm trong ~[1, 10^{18}]~ (thành công), và khi đó cập nhật ~x \leftarrow x + y~. Nếu không, trả ~0~ và ~x~ không đổi.

• ~\texttt{mul}~ ~y~: nhân ~x~ với số nguyên dương ~y~ (~1 \le y \le 10^{18}~). Jury trả ~1~ nếu ~x \cdot y~ nằm trong ~[1, 10^{18}]~ (thành công), và khi đó cập nhật ~x \leftarrow x \cdot y~. Nếu không, trả ~0~ và ~x~ không đổi.

• ~\texttt{div}~ ~y~: chia ~x~ cho số nguyên dương ~y~ (~1 \le y \le 10^{18}~). Jury trả ~1~ nếu ~x~ chia hết cho ~y~ (thành công), và khi đó cập nhật ~x \leftarrow \frac{x}{y}~. Nếu không, trả ~0~ và ~x~ không đổi.

• ~\texttt{digit}~: thay ~x~ bằng tổng chữ số của nó. Jury luôn trả ~1~ và cập nhật ~x \leftarrow S(x)~.

Lưu ý, lệnh có phân biệt chữ hoa/thường.

Khi bạn tin rằng ~x = n~, in ra ~!~. Jury sẽ trả ~1~ nếu ~x~ đúng bằng ~n~, và ~-1~ nếu ngược lại. Lệnh ~!~ không tính vào giới hạn ~7~ lệnh.

Sau mỗi lần in lệnh, bạn phải xuống dòng và flush output, nếu không sẽ bị ~\texttt{Idleness limit exceeded}~. Để flush output, dùng:

• fflush(stdout) hoặc cout.flush() với C++.

• System.out.flush() với Java.

• sys.stdout.flush() với Python.

• std::io::stdout().flush() với Rust.

• Với các ngôn ngữ khác, vui lòng tham khảo documentation.

Nếu chương trình của bạn dùng quá ~7~ lệnh cho một test case, hoặc in ra lệnh không hợp lệ, jury sẽ trả ra ~-1~. Sau khi nhận ~-1~, chương trình của bạn phải kết thúc ngay lập tức để nhận verdict ~\texttt{Wrong Answer}~. Ngược lại, bạn có thể nhận bất kì verdict nào.

Interactor là non-adaptive: số nguyên bí mật ~x~ không thay đổi trong suốt quá trình tương tác.

Scoring

Gọi ~\tau~ là số lệnh lớn nhất của từng case bạn dùng trong một test:

• Nếu ~5 \le \tau \le 7~, bạn nhận được ~30\%~ điểm của test đó.

• Nếu ~\tau = 4~, bạn nhận được ~70\%~ điểm của test đó.

• Nếu ~\tau<4~, số lệnh của bạn sẽ được so sánh với số lệnh của ban giám khảo, nếu ~\tau~ không lớn hơn giá trị của ban giám khảo, bạn nhận được toàn bộ số điểm, ngược lại nhận được ~90\%~ điểm của test.

Sample Input 1

3
9

1

0

1

1

67

1

1

420

-1

Sample Output 1

div 2

mul 1000000000000000000

digit

!

add -2

!

!

Notes

Lưu ý dòng trống trong ví dụ chỉ để giúp cho người đọc dễ quan sát, và sẽ không xuất hiện trong quá trình tương tác thực tế.

Bạn đang tìm một vị trí trong đất để đặt một con giun, thú cưng của mình, Maximus. Khu vực tìm kiếm là một vùng hình hộp có kích thước ~N \times M \times K~ được chia thành lưới ba chiều gồm các ô hình lập phương. Các ô trong hộp được gắn nhãn ~(x, y, z)~, tương ứng với tọa độ của chúng ~(1 \leq x \leq N, 1 \leq y \leq M, 1 \leq z \leq K)~. Mỗi ô có độ ẩm nhất định ~H [x, y, z]~ là một số nguyên trong phạm vi ~1 ... 10^9~. Bạn có thể đo độ ẩm của bất kỳ ô nào bằng một cảm biến đặc biệt.

Maximus rất thích những nơi ẩm ướt, vì vậy bạn cần phải đưa nó vào một ô có độ ẩm ướt không thấp hơn các ô lân cận, nếu không, nó sẽ bỏ đi và bạn sẽ khó tìm thấy nó. Nói cách khác, bạn cần đặt Maximus ở ô ~(x, y, z)~, sao cho:

~H [x, y, z] \geq max (H [x + 1, y, z],\ H [x - 1, y, z],\ H [x, y + 1, z],\ H [x, y - 1, z],\ H [x, y, z + 1],\ H [x, y, z - 1])~

Trong đó, một giá trị được coi là ~0~ khi nó nằm ngoài hộp (vì Maximus muốn ở trong hộp). Tuy nhiên, số lượng ô có thể rất lớn, vì vậy bạn không thể đo độ ẩm của tất cả các ô. Do đó, bạn chỉ có thể đo một số lượng ô nhất định.

Interaction

Đầu tiên, bạn cần đọc vào bốn số nguyên ~N, M, K, Q~. Trong đó ~N, M, K~ là kích thước hình hộp và ~Q~ là số truy vấn bạn được hỏi. Sau đó bạn được phép hỏi chương trình các câu như sau:

• ? x y z (~1 \le x \le N~, ~1 \le y \le M~, ~1 \le z \le K~): chương trình sẽ in ra giá trị ~H[x, y, z]~, lưu ý rằng bạn không được hỏi quá ~Q~ truy vấn này.

• ! x y z (~1 \le x \le N~, ~1 \le y \le M~, ~1 \le z \le K~): vị trí bạn chọn cho Maximus. Lưu ý rằng bạn chỉ được trả lời một lần duy nhất và chương trình sẽ dừng lại sau đó. Câu trả lời cần thỏa mãn điều kiện đề bài.

Sau mỗi lần in lệnh, bạn phải xuống dòng và flush output, nếu không sẽ bị ~\texttt{Idleness limit exceeded}~. Để flush output, dùng:

• fflush(stdout) hoặc cout.flush() với C++.

• System.out.flush() với Java.

• sys.stdout.flush() với Python.

• std::io::stdout().flush() với Rust.

• Với các ngôn ngữ khác, vui lòng tham khảo documentation.

Interactor là non-adaptive: độ ẩm không thay đổi trong suốt quá trình tương tác.

Scoring

Sample Input 1

3 1 1 3

1

1

3

Sample Output 1

? 1 1 1

? 2 1 1

? 3 1 1

! 3 1 1

Notes

Quá trình tương tác giữa máy chấm và chương trình của bạn:

Bạn cần đoán một xâu bí mật ~s~ độ dài ~n~ chỉ gồm các ký tự ~\{a, b, c\}~.

Để làm vậy, bạn có thể thực hiện truy vấn sau:

• ~?~ ~t~ — bạn chọn một xâu ~t~ bất kỳ và hệ thống trả về độ dài xâu con chung dài nhất (LCS) của ~s~ và ~t~.

Khi bạn đã biết chính xác xâu ~s~, hãy in ra kết quả.

Lưu ý: Số lượng truy vấn không được vượt quá ~\left\lfloor \frac{5}{3} n \right\rfloor + 1~.

Input

Ban đầu, bạn cần đọc vào số nguyên ~n~ ~(1 \le n \le 1000)~ — độ dài của xâu bí mật ~s~.

Interaction

Để thực hiện truy vấn, in ra "? t" và đọc vào một số nguyên — độ dài LCS của ~s~ và ~t~. Xâu ~t~ phải là xâu không rỗng chỉ gồm các ký tự ~\{a, b, c\}~.

Khi đã biết kết quả, in ra "! s" — xâu bí mật ~s~. Chương trình của bạn phải kết thúc sau khi in ra kết quả này.

Nếu bạn nhận được kết quả là ~-1~ khi thực hiện truy vấn thì bạn đã thực hiện nhiều lượt truy vấn hơn cho phép hoặc thực hiện một truy vấn không hợp lệ. Chương trình của bạn phải kết thúc ngay và sẽ nhận được kết quả Wrong Answer.

Scoring

• Số lượng truy vấn không vượt quá ~\left\lfloor \frac{5}{3} n \right\rfloor + 1~

Sample Input 1

4
2
1

Sample Output 1

? aa
? bb
! abac

Notes

Xâu bí mật là ~s = \texttt{"abac"}~, ~n = 4~.

• Truy vấn "aa": ~LCS(\texttt{"abac"}, \texttt{"aa"}) = 2~.

• Truy vấn "bb": ~LCS(\texttt{"abac"}, \texttt{"bb"}) = 1~.

• Các truy vấn tiếp theo đoán đúng ~s = \texttt{"abac"}~.

Hôm nay, lớp của Cam có một trò chơi trong giờ Toán. Có n miếng gà: ~p[0], p[1], \ldots, p[n - 1]~. Trong số đó có một miếng ngon nhất bí mật là ~p[b]~.

Bạn được so sánh độ ngon giữa hai miếng gà thông qua hàm find_better(i, j), hàm sẽ trả về chỉ số của miếng gà ngon hơn.

Mục tiêu: Tìm ra chỉ số của miếng gà ngon nhất, đồng thời tối ưu số lần gọi hàm find_better() trên miếng gà ngon nhất.

Interaction

Đầu tiên, đọc số nguyên ~n~ ~(2 \leq n \leq 10^5)~ trên một dòng.

Để tương tác với trình chấm, in mỗi lệnh trên một dòng riêng, lưu ý phải flush output bằng fflush(stdout) hoặc cout.flush.

Các câu lệnh:

• ? i j: Trình chấm gọi find_better(i, j) và trả về chỉ số của miếng gà ngon hơn.

• answer b: Trả lời chỉ số của miếng gà ngon nhất là ~p[b]~ mà bạn tìm được. Chương trình phải in answer chính xác một lần.

Scoring

Nếu chương trình đưa ra kết quả answer sai, hoặc dùng quá ~10^6~ lần hỏi, hoặc bị lỗi làm chương trình kết thúc bất thường thì test đó sẽ nhận ~0~ điểm.

Ngược lại, gọi ~T~ là điểm tối đa của test đó, ~L~ là đáp án của giám khảo, và ~X~ là số lần chương trình của thí sinh gọi hàm find_better() trên miếng ngon nhất. Số điểm thí sinh nhận được cho test này được tính theo công thức:

$$\text{Điểm} = \begin{cases} T & \text{nếu } X \le L \\ \frac{\max(0, 100 - (X - L) \cdot 6)}{100} \cdot T & \text{nếu } X > L \end{cases}$$

Notes

Giả sử độ ngon của mỗi miếng lần lượt là ~[0, 3, 1, 2]~

Đây là một bài toán interactive.

Bạn sẽ thực hiện ~t~ ván khác nhau tại trò chơi dò mìn.

Mỗi ván đấu, bạn sẽ chơi trên một lưới ô vuông gồm ~n~ hàng và ~m~ cột, mỗi ô sẽ ở trong trạng thái có mìn hoặc không có mìn (lưu ý rằng kích thước lưới ô vuông và trạng thái các ô có thể khác nhau qua các ván đấu). Nhưng bạn không biết trạng thái của các ô là thế nào cả, trừ việc có tổng cộng ~k~ ô có mìn.

Bạn có thể dò một ô bất kỳ để biết nó có mìn hay không. Nếu nó có mìn, bạn sẽ thêm ~1~ điểm phạt (trước mỗi trò chơi, bạn có ~0~ điểm phạt); nếu nó không có mìn, bạn sẽ biết được số ô có mìn trong ~8~ ô vuông gần với nó nhất.

Mục tiêu cuối cùng của bạn là phải tìm được vị trí tất cả các ô có mìn, sao cho điểm phạt là bé nhất có thể.

Để làm điều này, bạn sẽ nộp một lời giải cho máy chấm. Quá trình kiểm tra lời giải của bạn diễn ra như sau:

• Lời giải của bạn có thể dò ô tại hàng thứ ~x~ - cột thứ ~y~ bằng cách lần lượt in ra ~x~ và ~y~ trên một dòng.

  • Nếu ô này có mìn, máy chấm sẽ in ra ~-1~.

  • Nếu không, máy chấm sẽ in ra số ô có mìn trong ~8~ ô vuông gần với ô tại hàng thứ ~x~-cột thứ ~y~ nhất.

• Lời giải của bạn có thể tuyên bố rằng đã tìm được tất cả các ô có mìn bằng cách in ra hai số ~0~ trên một dòng, và ~k~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương là chỉ số hàng và chỉ số cột của các ô có mìn.

  • Nếu danh sách các ô có mìn là đúng, số điểm bạn nhận được phụ thuộc vào số lượng số ~-1~ mà máy chấm in ra, kích cỡ trò chơi, và số lượng mìn.

  • Ngược lại, bạn sẽ nhận được ~0~ điểm.

• Trước khi tuyên bố rằng đã tìm được tất cả các ô có mìn, bạn có thể tiếp tục dò các ô bất cứ số lần nào.

Input

Ban đầu, bạn được nhận một số nguyên dương duy nhất là ~t~ ~(t=5)~. Mỗi lượt chơi bắt đầu như sau:

• Máy chấm lần lượt in ra ~3~ số nguyên dương là ~n~, ~m~, và ~k~ ~(5 \leq n \leq m \leq 100; 1 \leq 4k \leq nm)~.

• Sau mỗi lần dò của bạn, bạn sẽ nhận thêm một số nguyên là câu trả lời của máy chấm.

• Nếu bạn đã tuyên bố rằng đã tìm được tất cả các ô có mìn, lượt chơi hiện tại kết thúc và lượt chơi tiếp theo (nếu có) bắt đầu.

Dữ liệu đầu vào đảm bảo các ô có mìn không thay đổi trong quá trình tương tác, không thay đổi qua các lần nộp, được gieo với phân phối ngẫu nhiên và đồng xác suất.

Máy chấm đảm bảo trạng thái có mìn hay không có mìn của các ô trong một ván đấu không thay đổi.

Output

Mỗi lượt chơi bắt đầu như sau:

• Lời giải nhận được ~3~ số nguyên dương là ~n~, ~m~, và ~k~ từ máy chấm.

• Lời giải có thể dò một ô trên lưới ô vuông, hoặc tuyên bố rằng đã tìm được tất cả các ô có mìn.

• Nếu bạn chưa tuyên bố rằng đã tìm được tất cả các ô có mìn, bạn có thể tiếp tục dò những ô khác.

Việc không in ra kết quả theo định dạng trên có thể gây ra lỗi và ảnh hưởng đến điểm số cuối cùng của bạn.

Interaction

Scoring

Công thức tính điểm của bạn tại mỗi lượt chơi sẽ được ẩn. Bạn được biết một số tính chất về nó như sau:

• Đảm bảo rằng tồn tại ~k~ không âm sao cho nếu bạn dò không quá ~k~ ô có mìn thì bạn nhận điểm tuyệt đối.

• Đảm bảo rằng dò ít ô có mìn hơn sẽ làm điểm cao hơn (nếu điểm chưa là điểm tuyệt đối).

• Đảm bảo rằng công thức chỉ phụ thuộc vào ~n~, ~m~, và ~k~.

Điểm của một bộ dữ liệu là điểm thấp nhất của các lượt chơi.

Notes

Giải thích ví dụ:

Nếu bạn sử dụng C++, hãy thêm lệnh 'cout<<endl' hoặc 'cout.flush()' sau mỗi truy vấn để máy chấm có thể nhận thông tin từ bạn.