Các giám khảo đang xây dựng chiến lược cho chương trình của ban giám khảo cho phiên bản sửa đổi của bài toán J từ kỳ thi hiện tại.

Trong bài toán đó, Alice bí mật tạo ra một hoán vị của $N$ số nguyên đầu tiên $a_1, a_2, \dots, a_N$ và cho Bob biết $N$. Bob đặt một số câu hỏi để xác định hoán vị này. Alice có thể thay đổi hoán vị trong quá trình này miễn là nó nhất quán với các câu trả lời trước đó của cô ấy.

Ban giám khảo dự định tạo ra một AliceBot sẽ thực hiện các công việc sau.

Có hai giai đoạn: giai đoạn đặt câu hỏi và giai đoạn trả lời.

Trong giai đoạn đặt câu hỏi, giám khảo thông báo cho AliceBot một số nguyên $N$. Sau đó, AliceBot phải trả lời một số câu hỏi mà giám khảo đặt ra về hoán vị.

Trong giai đoạn trả lời tiếp theo, AliceBot phải tạo ra hai hoán vị khác nhau $a_1, \dots, a_N$ và $b_1, \dots, b_N$ nhất quán với các câu trả lời từ giai đoạn trước.

Giám khảo đặt câu hỏi có độ kiên nhẫn ban đầu $P = 2N$. Mỗi khi giám khảo đặt một câu hỏi, độ kiên nhẫn của giám khảo sẽ giảm xuống.

Có ba loại câu hỏi mà giám khảo có thể đặt ra:

• Loại 1, có định dạng “? 1 i j k”: giám khảo chọn ba số nguyên khác nhau $i, j, k$ ($1 \le i, j, k \le N$), AliceBot xem xét ba số nguyên $a_i, a_j$ và $a_k$, rồi cho Bob biết giá trị trung vị của chúng (giá trị không phải là nhỏ nhất cũng không phải là lớn nhất). Mỗi câu hỏi như vậy làm giảm độ kiên nhẫn của giám khảo đi 2.
• Loại 2, có định dạng “? 2 i j”: giám khảo chọn hai số nguyên khác nhau $i, j$ ($1 \le i, j \le N$), và AliceBot trả lời $i$ nếu $a_i < a_j$, hoặc $j$ nếu ngược lại. Mỗi câu hỏi như vậy làm giảm độ kiên nhẫn của giám khảo đi 2.
• Loại 3, có định dạng “? 3 i j”: giám khảo chọn hai số nguyên khác nhau $i, j$ ($1 \le i, j \le N$), và AliceBot cho biết giá trị nhỏ nhất trong số $a_i$ và $a_j$. Mỗi câu hỏi như vậy làm giảm độ kiên nhẫn của giám khảo đi 1.

Bạn có thể giả định rằng độ kiên nhẫn của giám khảo sẽ không bao giờ xuống dưới 2 sau khi đặt câu hỏi. Khi giám khảo quyết định rằng họ đã đặt đủ câu hỏi, lệnh “!” được gửi đến AliceBot, chuyển nó sang giai đoạn trả lời.

Trong giai đoạn trả lời, AliceBot thông báo cho giám khảo hai hoán vị $a_1, \dots, a_N$ và $b_1, \dots, b_N$. Hai hoán vị này phải nhất quán với tất cả các câu trả lời đã đưa ra trong giai đoạn đặt câu hỏi, và số lượng vị trí $i$ sao cho $a_i = b_i$ phải ít nhất là $\lceil p/2 \rceil$, trong đó $p$ là độ kiên nhẫn của giám khảo khi kết thúc giai đoạn đặt câu hỏi.

Vì giám khảo quá lười biếng, bạn được yêu cầu triển khai AliceBot. Có thể chứng minh rằng bài toán có thể giải được cho mọi $N$ có thể từ các giới hạn.

Giao tiếp

Đầu tiên, chương trình của ban giám khảo gửi cho bạn một số nguyên $N$ trên một dòng riêng biệt ($4 \le N \le 50\,000$).

Sau đó, ban giám khảo đặt các câu hỏi.

Một câu hỏi loại 1 là một dòng có định dạng “? 1 i j k” ($1 \le i, j, k \le N$; $i, j$ và $k$ đôi một khác nhau). Sau đó, bạn in ra một dòng với một số nguyên duy nhất: giá trị trung vị của các giá trị $a_i, a_j$ và $a_k$.

Một câu hỏi loại 2 là một dòng có định dạng “? 2 i j” ($1 \le i, j \le N$; $i \neq j$). Sau đó, bạn in ra một dòng với một số nguyên duy nhất: $i$ nếu $a_i < a_j$, hoặc $j$ nếu $a_i > a_j$.

Một câu hỏi loại 3 là một dòng có định dạng “? 3 i j” ($1 \le i, j \le N$; $i \neq j$). Sau đó, bạn in ra một dòng với một số nguyên duy nhất: giá trị nhỏ nhất trong số $a_i$ và $a_j$.

Giả sử có tổng cộng $q_1$ câu hỏi loại 1, $q_2$ câu hỏi loại 2 và $q_3$ câu hỏi loại 3. Bạn có thể giả định rằng giá trị $p = 2N - 2q_1 - 2q_2 - q_3$ không nhỏ hơn 2.

Để chuyển sang giai đoạn trả lời, chương trình của ban giám khảo đưa ra một dòng bao gồm ký hiệu ‘!’. Sau đó, bạn phải in hai dòng, dòng đầu tiên chứa $N$ số nguyên cách nhau bởi dấu cách $a_1, \dots, a_N$, và dòng thứ hai chứa $N$ số nguyên cách nhau bởi dấu cách $b_1, \dots, b_N$. Mỗi dãy trong hai dãy này phải là một hoán vị của $1, \dots, N$, và chúng phải nhất quán (tức là bằng nhau) tại ít nhất $\lceil p/2 \rceil$ vị trí.

Đừng quên in ký tự xuống dòng và xóa bộ đệm đầu ra sau khi in các câu trả lời và sau khi in mỗi hoán vị, nếu không, bạn có thể gặp lỗi “Idleness Limit Exceeded”.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4
4
1
3 5 4 1 2
5 4 3 2 1