Có $N$ tay đua xe đạp $1, \dots, N$. Mỗi tay đua có một kỹ năng riêng biệt từ $1$ đến $N$, và khi hai tay đua đối đầu, tay đua có kỹ năng cao hơn luôn thắng.
Các tay đua thích tham gia các cuộc thi. Trong một cuộc thi, các tay đua được sắp xếp theo một danh sách vòng tròn. Cuộc thi sau đó diễn ra theo từng vòng. Trong mỗi vòng, một tay đua sẽ đua với từng người hàng xóm của mình. Nếu họ thua cả hai người hàng xóm, họ sẽ bị loại.
Bạn không biết kỹ năng của các tay đua và muốn tìm ra chúng. Bạn có thể tổ chức các cuộc thi cho tất cả các tay đua, chọn cách sắp xếp họ trong danh sách vòng tròn mỗi lần, và sẽ được thông báo tay đua nào bị loại ở vòng nào.
Hãy tìm ra kỹ năng của các tay đua bằng số lượng cuộc thi tối ưu, hoặc sử dụng $N$ cuộc thi để nhận điểm một phần.
Giao tiếp
Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Quá trình tương tác bắt đầu với một dòng chứa số nguyên duy nhất $T$ ($1 \le T \le 10^4$), số lượng trường hợp thử nghiệm.
Mỗi trường hợp thử nghiệm bắt đầu với một dòng chứa số nguyên duy nhất $N$ ($3 \le N \le 300$), số lượng tay đua.
Sau đó, bạn có thể tổ chức các cuộc thi. Để tổ chức một cuộc thi, hãy in một dòng “? $a_1$ $a_2$ \dots $a_n$” — $a_k$ cho biết tay đua $a_k$ ở vị trí thứ $k$ trong danh sách tay đua. Danh sách $a_1, \dots, a_n$ phải là một hoán vị của $1, \dots, n$.
Câu trả lời cho truy vấn của bạn sẽ là một dòng “$r_1$ $r_2$ \dots $r_n$” — $r_k$ thỏa mãn $0 \le r_k < n$. Khi $r_k > 0$, nó cho biết tay đua ở vị trí thứ $k$ đã bị loại ở vòng $r_k$ của cuộc thi. Nếu $r_k = 0$, thì tay đua đó đã thắng cuộc thi.
Sau khi bạn đã xác định được kỹ năng của các tay đua, hãy in một dòng “! $s_1$ $s_2$ \dots $s_n$” — $s_k$ phải bằng kỹ năng của tay đua $k$.
Nếu bạn thực hiện một truy vấn không hợp lệ hoặc cố gắng tổ chức nhiều hơn $N$ cuộc thi, giải pháp của bạn sẽ nhận được phán quyết Wrong Answer. Ngoài ra, nếu tập hợp kỹ năng bạn in ra khác với tập hợp kỹ năng mà trình tương tác đang giữ, giải pháp của bạn sẽ nhận được phán quyết Wrong Answer. Trong cả hai trường hợp, quá trình tương tác sẽ kết thúc ngay lập tức. Nếu không, bạn sẽ nhận được điểm như được mô tả trong phần chấm điểm.
Lưu ý rằng trình tương tác có thể thích nghi: kỹ năng thực sự của các tay đua có thể thay đổi trong suốt quá trình tương tác, nhưng tập hợp kỹ năng hiện tại sẽ luôn nhất quán với tất cả các cuộc thi trước đó.
Nhiệm vụ con
Đối với mỗi trường hợp thử nghiệm, gọi $q$ là số lượng cuộc thi mà giải pháp của bạn đã tổ chức. Ngoài ra, đối với mỗi $N$, gọi $c_N$ là số lượng cuộc thi tối thiểu cần thiết để đảm bảo có thể xác định được kỹ năng.
Bạn sẽ nhận được 100 điểm nếu $q \le c_N$ cho tất cả các trường hợp thử nghiệm. Nếu không, bạn sẽ nhận được 10 điểm. Lưu ý rằng theo các ràng buộc của bài toán, việc nhận được 10 điểm yêu cầu bạn phải thỏa mãn $q \le N$ cho tất cả các trường hợp thử nghiệm.
Ví dụ
Dữ liệu vào 1
1 5 Fixed 4 2 1 5 3
Dữ liệu ra 1
? 1 2 3 4 5 3 2 1 0 1 ? 1 3 5 2 4 3 1 2 1 0 ? 1 4 2 5 3 3 0 1 2 1 ? 1 5 4 3 2 3 1 0 1 2 ! 4 2 1 5 3
Ghi chú
Trong ví dụ, kỹ năng của các tay đua lần lượt là 4, 2, 1, 5, 3.
Trong cuộc thi đầu tiên được tổ chức, các tay đua được sắp xếp vào danh sách vòng tròn $[1, 2, 3, 4, 5]$. Cuộc thi diễn ra như sau; trong mỗi vòng, danh sách tay đua được hiển thị với các tay đua bị loại được thay thế bằng $X$.
Trong vòng 1:
- Tay đua ở vị trí 3 (tay đua 3 với kỹ năng 1) thua các tay đua ở vị trí 2 và 4 (tay đua 2, 4 với kỹ năng 2, 5) và bị loại.
- Tay đua ở vị trí 5 (tay đua 5 với kỹ năng 3) thua các tay đua ở vị trí 4 và 1 (tay đua 4, 1 với kỹ năng 5, 4) và bị loại.
- Tay đua ở vị trí 1 (tay đua 1 với kỹ năng 4) thắng các tay đua ở vị trí 5, 2 (tay đua 5, 2 với kỹ năng 3, 2) và do đó không bị loại.
- Tay đua ở vị trí 2 (tay đua 2 với kỹ năng 2) thắng tay đua ở vị trí 3 (tay đua 3 với kỹ năng 1) và do đó không bị loại.
- Tay đua ở vị trí 4 (tay đua 4 với kỹ năng 5) thắng các tay đua ở vị trí 3, 5 (tay đua 3, 5 với kỹ năng 1, 3) và do đó không bị loại.
Trong vòng 2, danh sách tay đua là $[1, 2, X, 4, X]$.
- Tay đua ở vị trí 2 thua các tay đua ở vị trí 1 và 4 và bị loại.
- Tay đua ở vị trí 1 thắng tay đua ở vị trí 2 và do đó không bị loại.
- Tay đua ở vị trí 4 thắng hai tay đua còn lại và do đó không bị loại.
Trong vòng 3, danh sách tay đua là $[1, X, X, 4, X]$.
- Tay đua ở vị trí 1 thua các tay đua ở vị trí 4 và 4 (cùng là một tay đua) và bị loại.
- Tay đua ở vị trí 4 thắng tay đua ở vị trí 1 và do đó không bị loại.
Do đó, Tay đua ở vị trí 1 bị loại ở vòng 3. Tay đua ở vị trí 2 bị loại ở vòng 2. Tay đua ở vị trí 3 bị loại ở vòng 1. Tay đua ở vị trí 4 thắng cuộc thi. * Tay đua ở vị trí 5 bị loại ở vòng 1.
tạo ra câu trả lời cho truy vấn $[3, 2, 1, 0, 1]$.
Trong cuộc thi thứ hai được tổ chức, các tay đua được sắp xếp vào danh sách vòng tròn $[1, 3, 5, 2, 4]$. Cuộc thi diễn ra như sau.
Trong vòng 1:
- Tay đua ở vị trí 2 (tay đua 3 với kỹ năng 1) thua các tay đua ở vị trí 1 và 3 (tay đua 1, 5 với kỹ năng 4, 3) và bị loại.
- Tay đua ở vị trí 4 (tay đua 2 với kỹ năng 2) thua các tay đua ở vị trí 3 và 5 (tay đua 5, 4 với kỹ năng 3, 5) và bị loại.
- Tay đua ở vị trí 1 (tay đua 1 với kỹ năng 4) thắng tay đua ở vị trí 2 (tay đua 3 với kỹ năng 1) và do đó không bị loại.
- Tay đua ở vị trí 3 (tay đua 5 với kỹ năng 3) thắng các tay đua ở vị trí 2, 4 (tay đua 3, 2 với kỹ năng 1, 2) và do đó không bị loại.
- Tay đua ở vị trí 5 (tay đua 4 với kỹ năng 5) thắng các tay đua ở vị trí 4, 1 (tay đua 2, 1 với kỹ năng 2, 4) và do đó không bị loại.
Trong vòng 2, danh sách tay đua là $[1, X, 5, X, 4]$.
- Tay đua ở vị trí 3 thua các tay đua ở vị trí 1 và 5 và bị loại.
- Tay đua ở vị trí 1 thắng tay đua ở vị trí 3 và do đó không bị loại.
- Tay đua ở vị trí 5 thắng hai tay đua còn lại và do đó không bị loại.
Trong vòng 3, danh sách tay đua là $[1, X, X, X, 4]$.
- Tay đua ở vị trí 1 thua các tay đua ở vị trí 5 và 5 (cùng là một tay đua) và bị loại.
- Tay đua ở vị trí 5 thắng tay đua ở vị trí 1 và do đó không bị loại.
Do đó, Tay đua ở vị trí 1 bị loại ở vòng 3. Tay đua ở vị trí 2 bị loại ở vòng 1. Tay đua ở vị trí 3 bị loại ở vòng 2. Tay đua ở vị trí 4 bị loại ở vòng 1. * Tay đua ở vị trí 5 thắng cuộc thi.
tạo ra câu trả lời cho truy vấn $[3, 1, 2, 1, 0]$.