Đây là bài tương tác, hãy đọc hướng dẫn làm bài tương tác ở đây.

Cửa hàng VNOI gồm ~n~ món đồ, món đồ thứ ~i~ có giá ~p_i~. Các món đồ đều có giá đôi một phân biệt với nhau.

Bạn muốn mua toàn bộ các món đồ trong cửa hàng. Chủ cửa hàng nhận ra bạn là một khách VIP nên đưa cho bạn một voucher khuyến mãi như sau: bạn sẽ được miễn phí ~k~ món đồ, và phải trả tiền cho ~n- k~ món đồ còn lại. Tuy nhiên, điều thú vị ở đây là, bạn sẽ không biết giá trị của các món đồ, mà chỉ biết về các tham số ~n~ và ~k~ tương đương với số lượng món đồ và số món đồ được miễn phí.

Bạn muốn tối đa hóa lợi ích cho mình, nên muốn chọn các món đồ sao cho tổng số tiền các món đồ bạn phải trả là ít nhất có thể.

Tất nhiên, bạn sẽ được hỏi ông chủ những câu có dạng như sau, với mỗi lượt được quyền chọn hai số ~x~ và ~y~:

• ~?~ ~x~ ~y~ trong đó ~1\le x,y\le n~.
• Sau mỗi truy vấn bạn dùng ~endl~ để ngắt câu hỏi.
• Máy chấm sẽ đọc truy vấn và in về một số nguyên:
  • Nếu ~p[x] < p[y]~, in về y.
  • Ngược lại (khi ~p[x] > p[y]~), in về x.

Bạn không được trực tiếp đọc hay in giá trị của ~p[i]~ - chỉ so sánh thông qua các truy vấn trên.

Ở bài toán này, điểm số ở từng test của bạn sẽ được chấm bằng một hàm bí mật, chỉ biết rằng, gọi ~C_u~ là số thao tác mà bạn sử dụng, ~C_j~ là số thao tác mà giám khảo sử dụng:

• Nếu ~C_u \le C_j~ bạn sẽ được toàn bộ số điểm của test đó.
• Ngược lại, số điểm mà bạn nhận được sẽ được tính toán sao cho nếu ~C_u - C_j~ càng nhỏ, điểm số càng cao.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le n \le 10^3~, ~1 \le k \le n~) – số lượng món đồ và số món đồ được miễn phí.

• Sau khi đọc dòng này bạn sẽ bắt đầu quá trình tương tác.

Interaction

Để hỏi một truy vấn so sánh giá của hai món đồ ~x~ và ~y~, chương trình của bạn cần in "~?~ ~x~ ~y~" (với ~1 \le x, y \le n~).

Sau đó chương trình của bạn cần đọc kết quả do hệ thống cung cấp:

• Nếu ~p[x] < p[y]~, hệ thống trả về ~y~.
• Ngược lại (khi ~p[x] > p[y]~), hệ thống trả về ~x~.

Bạn không được dùng quá ~10^6~ truy vấn trong toàn bộ quá trình.

Để đưa ra đáp án, chương trình của bạn cần in "~!~ ~1~ ~1~", sau đó trên dòng tiếp theo in ra ~k~ số ~id_1, id_2, ..., id_k~ đôi một phân biệt là các món đồ mà bạn chọn để miễn phí. Việc đưa ra đáp án không tính vào số câu hỏi.

Sau khi in ra một truy vấn, bạn cần xuống dòng và flush output. Để làm điều này, hãy:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• flush(output) trong Pascal;
• stdout.flush() trong Python;

Example

Giả sử các món đồ có giá ẩn là ~p=[2,\,5,\,1,\,4,\,3]~, ~n=5~, và ~k=2~.

Trong ví dụ dưới đây, các truy vấn giúp xác định được món đồ ~2~ và ~4~ là hai món đồ có giá cao nhất để chọn miễn phí.

Sample Input

5 2

3

3

4

1

Sample Output

? 1 3

? 3 5

? 4 2

? 1 4

! 1 1
2 4

Lưu ý

• Mỗi truy vấn in đúng cú pháp ? x y rồi endl.
• Tổng số truy vấn không vượt quá ~10^6~.
• Khi hoàn thành, in ! 1 1 rồi dòng chứa đáp án.
• Đáp án bị coi là sai nếu dùng quá nhiều truy vấn hoặc in sai định dạng.