Đây là bài toán tương tác. Hãy nhớ đẩy dữ liệu khỏi bộ đệm đầu ra sau mỗi lần in. Bạn có thể dùng:

• fflush(stdout) hoặc cout.flush() trong C/C++;
• System.out.flush() trong Java và Kotlin;
• sys.stdout.flush() trong Python;
• Xem tài liệu đối với các ngôn ngữ khác.

Little Cyan Fish có một hoán vị bí mật $p_0,p_1,\ldots,p_n$ độ dài $n+1$, gồm các số nguyên từ $0$ đến $n$. Cậu ấy muốn bạn đoán hoán vị bí mật này. Để làm điều đó, Little Cyan Fish cho phép bạn thực hiện không quá $1024$ truy vấn có dạng sau:

• ? i j: Nhận chỉ số $k$ ($0\le k\le n$) sao cho $p_k=|p_i-p_j|$.

Tất nhiên, để truy vấn hợp lệ, bạn phải bảo đảm $i$ và $j$ là hai số nguyên trong $[0,n]$. Ví dụ, nếu $p_0=2,p_1=0,p_2=1$, truy vấn ? 0 2 sẽ trả về chỉ số $2$, vì $|p_0-p_2|=|2-1|=1=p_2$.

Little Cyan Fish muốn bạn nghĩ ra một chiến lược tìm hoán vị. Tất nhiên, cậu ấy không muốn bạn thắng trò chơi quá dễ dàng. Vì vậy, cậu ấy sẽ thay đổi hoán vị $p$ một cách thích nghi để gài bẫy bạn (xem phần “Giao tiếp” để biết thêm chi tiết).

Dữ liệu vào

Có nhiều bộ dữ liệu kiểm thử. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1\le T\le100$), biểu thị số bộ dữ liệu kiểm thử.

Với mỗi bộ dữ liệu kiểm thử, dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ ($1\le n\le1000$). Sau đó, quá trình tương tác bắt đầu.

Giao tiếp

Để thực hiện truy vấn, in ra một dòng theo định dạng sau:

$$?\ i\ j$$

Ở đây $i$ và $j$ là hai số nguyên từ $0$ đến $n$. Bạn phải bảo đảm số truy vấn không vượt quá $1024$. Đáp lại truy vấn, bạn sẽ nhận được một số nguyên $k$ sao cho $p_k=|p_i-p_j|$.

Để báo cáo đáp án, in ra một dòng theo định dạng sau:

$$!\ p_0\ p_1\ \ldots\ p_n$$

Ở đây $p$ là hoán vị bạn muốn báo cáo.

Sau khi in truy vấn hoặc báo cáo đáp án, đừng quên in ký tự xuống dòng và đẩy dữ liệu khỏi luồng đầu ra.

Trong bài toán này, trình tương tác có tính thích nghi. Điều đó có nghĩa là hoán vị $p$ có thể thay đổi tùy theo các truy vấn của bạn, miễn là không mâu thuẫn với các truy vấn trước đó.

Ví dụ

Ví dụ giao tiếp 1

Đọc:

1
3

Ghi:

? 2 2

Đọc:

1

Ghi:

? 0 3

Đọc:

3

Ghi:

! 2 0 3 1

Công cụ kiểm thử: Một công cụ được cung cấp để giúp thí sinh phát triển và kiểm thử lời giải. Bạn có thể tải công cụ này từ các tệp đính kèm. Chạy công cụ với tùy chọn -h sẽ mô tả cách sử dụng. Công cụ chỉ triển khai một số kịch bản kiểm thử và một phần chức năng của chương trình chấm thực tế.