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

Vào năm 2023, ZaloPay cho ra mắt giải pháp "Mã QR đa năng", tích hợp chuẩn VietQR. Với tính năng này, người dùng có thể thoải mái sử dụng các ứng dụng Ngân hàng hoặc Ví điện tử để thực hiện các giao dịch thanh toán một cách nhanh chóng, tiện lợi và an toàn chỉ bằng cách quét mã Zalopay QR đa năng.

Khi quét mã VietQR bằng ứng dụng ZaloPay, người dùng có thể linh hoạt sử dụng nhiều nguồn tiền khác nhau (Tài khoản tích lũy, Tài khoản trả sau, Thẻ ghi nợ/ tín dụng và tài khoản internet banking) để thực hiện chuyển tiền đến tất cả ngân hàng hỗ trợ mã VietQR.

Khi biết đến tính năng này của ZaloPay, Jug rất hứng thú và ngay lập tức tạo cho mình một mã QR đa năng bằng cách mở ứng dụng ZaloPay hoặc ZaloPay trên ứng dụng Zalo, sau đó chọn chức năng "Nhận tiền" ngay trên Trang chủ. Tiếp theo, Jug nhập số tiền là một số nguyên dương ~X~ may mắn mà anh ấy rất thích rồi tiến hành tạo mã.

Vào một ngày không trăng không sao anh đến nhà Andy và thách Andy đoán được con số ~X~ trên QR đa năng mà Jug đã tạo. Nếu đoán đúng, Andy sẽ được tặng một món quà đặc biệt từ Jug.

Cũng là một người yêu lập trình, Jug cho phép Andy hỏi bất kì câu hỏi nào liên quan đến số ~X~, miễn là sử dụng các toán tử toán học hai ngôi tồn tại trong ngôn ngữ C++, bao gồm: ~>~, ~<~, ~=~, ~+~, ~-~, ~*~, ~/~ (chia lấy nguyên), ~\%~ (chia lấy dư), ~\&~ (and), ~|~ (or), ^ (xor), ~>>~ (logical 32-bit shift right), ~<<~ (logical 32-bit shift left). Kết quả trả về sẽ có kiểu Boolean, tức là chỉ có 2 giá trị ~true~ hoặc ~false~, biết một phép toán trả về kết quả có giá trị là ~false~ nếu kết quả của phép toán trả về giá trị đúng bằng ~0~, ngược lại kết quả sẽ về ~true~. Ví dụ ~(5 - 6)~, ~(6 / 5)~ hoặc ~(1 < 2)~ sẽ trả về ~true~, nhưng ~(4 / 5)~, ~(5 - 5)~, hoặc ~(1 = 2)~ sẽ trả về ~false~.

Để đưa ra câu hỏi, Andy phải sử dụng cú pháp:

• ? <toán tử> <toán hạng>

Trong đó: toán hạng là một số nguyên không âm có giá trị không quá ~10^9~, toán tử là 1 chuỗi kí tự thuộc tập >, <, =, +, -, *, /, %, >>, <<, &, |, ^.

Chú ý, nếu phép tính gặp các lỗi như divide by zero sẽ trả về ~false~.

Ví dụ: ! < 2, ý nghĩa câu hỏi này là X < 2 trả về kết quả dưới kiểu Boolean là gì (hoặc X bé hơn 2 có đúng không).

Những câu hỏi của Andy được đánh số bắt đầu từ 1.

Tuy nhiên cuộc sống không hề đơn giản, Jug vì cố tình làm khó Andy nên đã cố tình trả lời sai ở tối đa 1 câu bất kỳ mà Andy hỏi (tức là có 0 hoặc 1 lần Jug nói dối).

Để phát hiện Jug nói dối, Andy được hỗ trợ loại câu hỏi:

• @ <toán tử> <chỉ số câu hỏi>

Trong đó: toán tử thuộc tập ~\{<,>,=\}~, ví dụ @ < 5, cho biết từ câu hỏi 1 đến 4 Jug có nói dối không? Hay @ > 5 cho biết từ câu hỏi 6 đến câu hỏi hiện tại, Jug có trả lời dối không? Chỉ được hỏi với chỉ số câu hỏi là số nguyên không âm và không vượt quá chỉ số của câu hỏi hiện tại. Lưu ý, đối với câu hỏi loại này vẫn có thể bị nói dối, và bạn không thể biết được ở tương lai có nói dối không.

Sau khi chắc ăn đoán được số X, Andy sẽ đưa ra kết quả bằng cú pháp:

• ! X

Trong đó X là một số nguyên thể hiện kết quả mà Andy đoán, sau lệnh này chương trình sẽ dừng lại và cho điểm. Câu trả lời này không tính vào số lượng câu hỏi.

Yêu cầu: Jug giữ số ~X~ có giá trị trong khoảng ~[1..10^9]~. Là một nhà lập trình tài ba, với tối đa ~100~ câu hỏi, bạn hãy giúp Andy tìm ra được số ~X~ với số lần hỏi càng ít càng tốt.

Input

Sử dụng luồng nhập xuất chuẩn để đọc các câu trả lời từ Jug.

Ở dòng đầu tiên, bạn cần đọc một số nguyên dương ~T~ (~T \le 200~), là số lượng testcase trong một test đến từ Jug.

Sau khi đọc xong ~T~, quá trình tương tác cho từng testcase sẽ bắt đầu

Interaction

Để đưa ra một câu hỏi, hãy in ra câu hỏi thuộc một trong hai dạng sau:

1. ? opt num - ~0 \le num \le 10^9~
2. @ opt idx - ~0 \le idx \le currentIndex~ với ~currentIndex~ là chỉ số của câu hỏi hiện tại.

Sau khi đưa ra câu hỏi, bạn sẽ nhận được câu trả lời dưới dạng chuỗi có giá trị "true" hoặc "false". Bạn không được hỏi quá ~100~ câu hỏi.

Để đưa ra dự đoán, hãy in ra lệnh ! X, với ~X~ là kết quả dự đoán của bạn, sau khi đưa ra lệnh này chương trình sẽ kết thúc testcase hiện tại và bắt đầu testcase tiếp theo, lệnh đưa ra kết quả này không tính vào số lượng câu hỏi.

Mỗi truy vấn in trên một dòng, và cần flush sau khi in mỗi dòng, nếu không bạn có thể sẽ nhận được thông báo ~\texttt{Time limit exceeded}~.

• ~\texttt{fflush(stdout)}~ hoặc ~\texttt{cout.flush()}~ trong C++;
• ~\texttt{System.out.flush()}~ trong Java;
• ~\texttt{flush(output)}~ trong Pascal;
• ~\texttt{stdout.flush()}~ trong Python;
• Vui lòng xem tài liệu tại đây

Tính điểm

Jug sẽ chấm điểm cho một testcase như sau, gọi ~A~ là số lượng câu hỏi bạn sử dụng để tìm ra số ~X~, ~B~ là số lượng câu hỏi được cho là tốt nhất bởi tác giả để tìm ra đáp án (trong trường hợp xấu nhất).

• ~100\%~ điểm nếu ~A ≤ B~
• ~e^{-0.05 * (A - B)} * 100\%~ điểm nếu ~A > B~, với ~e \approx 2.718281828459045~ (càng sử dụng ít câu hỏi, điểm càng cao).
• ~0\%~ nếu ~A > 100~ hoặc Andy đoán sai.

Điểm của bạn sẽ được tính bằng ~min(score_i)~, với ~score_i~ là điểm cho testcase thứ ~i~, nói cách khác, bạn sẽ được tính điểm dựa trên testcase sử dụng nhiều câu hỏi nhất. Nếu có một testcase bạn đưa ra kết quả dự đoán sai, hoặc hỏi quá ~100~ câu, sẽ nhận về ~0~ điểm.

Ghi chú

Các phép toán thực hiện trên hệ thống có thể xảy ra tràn số như một chương trình bình thường, nếu kết quả phép toán vượt quá kiểu dữ liệu int64 (số nguyên có dấu 64 bit).

Khi bạn hỏi quá ~100~ câu, hệ thống sẽ kết thúc testcase hiện tại và bắt đầu testcase tiếp theo.

Khi bạn đưa ra câu hỏi không hợp lệ, chương trình sẽ kết thúc ngay lập tức với ~0~ điểm.

Sample

Input

1
? < 5
? < 3
@ = 1
? < 1
@ < 3
? – 4
! 4

Output

true
true
false
false
true
false

Notes

Ví dụ bên trên bao gồm 1 testcase, số ~X~ cần đoán là ~4~, và Jug đã nói dối ở câu có chỉ số là ~2~.

• Ở câu hỏi đầu, ? < 5 trả về true vì 4 < 5
• Ở câu hỏi thứ 2, ? < 3 trả về false vì 4 < 3 là sai, tuy nhiên Jug đã nói dối ở câu này nên câu trả lời là true
• Ở câu hỏi thứ 3, @ = 1 trả về false vì chỉ số của câu nói dối là ~2 \neq 1~
• Ở câu hỏi thứ 4, ? < 1 trả về false vì 4 < 1 là sai
• Ở câu hỏi thứ 5, @ < 3 trả về true vì chỉ số của câu nói dối là ~2 < 3~
• Ở câu hỏi thứ 6, ? - 4 trả về false vì 4-4=0 và 0 tương đương với false
• Dòng cuối lệnh ! 4 cho biết đáp án đưa ra là ~4~, chương trình sẽ lập tức kết thúc testcase này

Ở testcase trên sử dụng tất cả ~6~ câu hỏi