Truy Vấn XOR

Ban giám khảo giấu một hoán vị $p$ của các số nguyên từ $0$ đến $n-1$. Bạn chỉ biết độ dài $n$.

Gọi $b$ là hoán vị nghịch đảo của $p$, tức là $p_{b_i}=i$ với mọi $i$.

Thao tác duy nhất bạn được phép làm là chọn hai chỉ số $i$ và $j$ (không nhất thiết khác nhau) và hỏi giá trị $p_i\oplus b_j$, trong đó $\oplus$ là phép XOR theo bit.

Có thể có những hoán vị không phân biệt được với hoán vị ẩn, ngay cả khi bạn hỏi hết cả $n^2$ truy vấn. Cụ thể, một hoán vị $q$ với nghịch đảo $d$ được gọi là không phân biệt được với $p$ nếu

$$q_i\oplus d_j=p_i\oplus b_j\text{với mọi cặp }(i,j).$$

Nhiệm vụ của bạn là đếm số hoán vị không phân biệt được với hoán vị ẩn (tính cả chính nó) và in ra một hoán vị bất kỳ trong số đó, sử dụng không quá $2n$ truy vấn.

Hoán vị ẩn được cố định từ trước và không phụ thuộc vào các truy vấn của bạn.

Giao thức tương tác

Đây là bài toán tương tác. Chương trình của bạn giao tiếp với hệ thống chấm qua đầu vào/ra chuẩn.

Đầu tiên, chương trình đọc số nguyên $n$.

Sau đó bạn có thể thực hiện hai loại thao tác:

• ? i j (với $0\le i,j\le n-1$): Hỏi giá trị $p_i\oplus b_j$. Hệ thống trả về một số nguyên duy nhất là giá trị đó.

• Kết thúc: in ra ba dòng

  • dòng đầu chứa ký tự !,
  • dòng thứ hai chứa số nguyên $k$ là số hoán vị không phân biệt được với hoán vị ẩn,
  • dòng thứ ba chứa $n$ số nguyên $q_0,q_1,\dots ,q_{n-1}$ là một hoán vị không phân biệt được với hoán vị ẩn.

  Sau khi in đáp án, chương trình phải kết thúc ngay. Việc in đáp án không tính là một truy vấn.

Bạn được phép hỏi tối đa $2n$ truy vấn dạng ?. Nếu vượt quá giới hạn này, bài làm bị đánh giá là sai.

Quan trọng: Sau mỗi lần in ra, bạn phải flush output:

• C++: cout << endl; hoặc cout.flush();
• Python: print(..., flush=True)

Ràng buộc

• $1\le n\le 5000$
• Số truy vấn tối đa: $2n$

Ví dụ