Đây là một bài toán tương tác.

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 các câu hỏi để xác định hoán vị này. Anh ấy có thể đặt câu hỏi thuộc hai loại:

• Loại 1, có định dạng “? 1 i j k”: Bob chọn ba số nguyên khác nhau $i, j, k$ ($1 \le i, j, k \le N$), Alice xem xét ba giá trị $a_i, a_j$ và $a_k$, rồi trả lời cho Bob 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).
• Loại 2, có định dạng “? 2 i j”: Bob chọn hai số nguyên khác nhau $i, j$ ($1 \le i, j \le N$), và Alice trả lời $i$ nếu $a_i < a_j$, hoặc $j$ nếu ngược lại.

Trò chơi có vẻ quá dễ dàng đối với Bob, vì vậy Alice đã đặt ra các quy tắc mới. Thứ nhất, Bob chỉ được phép hỏi tối đa $2N$ câu hỏi loại 1 và chỉ 2 câu hỏi loại 2. Thứ hai, Alice có thể thay đổi hoán vị một cách tự do miễn là nó nhất quán với tất cả các câu trả lời đã đưa ra trước đó.

Hãy giúp Bob chiến thắng và viết chương trình xác định hoán vị đó.

Giao tiếp

Đầu tiên, chương trình giám khảo sẽ cho bạn biết một số nguyên $N$ trên một dòng riêng biệt ($4 \le N \le 60\,000$).

Sau đó, bạn có thể đặt 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). Chương trình giám khảo sau đó sẽ in ra một dòng với một số nguyên duy nhất: giá trị trung vị của $a_i, a_j$ và $a_k$. Bạn không được hỏi loại câu hỏi này quá $2N$ lần.

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$). Chương trình giám khảo sau đó sẽ 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$. Bạn không được hỏi loại câu hỏi này quá hai lần.

Khi hoán vị đã được xác định duy nhất, hãy in câu trả lời trên một dòng có định dạng “! a1 a2 ... aN ”.

Lưu ý rằng tương tác mang tính thích nghi: chương trình giám khảo có thể thay đổi hoán vị bất cứ lúc nào miễn là nó nhất quán với các câu trả lời trước đó. Đặc biệt, nếu bạn cố gắng đoán câu trả lời khi nó chưa được xác định duy nhất, chương trình giám khảo có thể ngay lập tức chọn một hoán vị khác và thông báo rằng bạn đã sai.

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

Ví dụ

Dữ liệu vào 1

5
4
4
2

Dữ liệu ra 1

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