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

Little Cyan Fish có một đồ thị vô hướng đơn ẩn gồm $n$ đỉnh, được đánh số từ $1$ đến $n$. Bạn biết giá trị của $n$, nhưng không biết bất kỳ cạnh nào của đồ thị. Little Cyan Fish rất yêu thích khái niệm lát cắt (cut). Với một tập hợp đỉnh $S$, gọi $\operatorname{cut}(S)$ là số lượng cạnh có đúng một đầu mút thuộc $S$.

Little Cyan Fish cho phép bạn so sánh các lát cắt bằng cách thực hiện truy vấn. Trong một truy vấn, bạn chọn hai tập hợp đỉnh $S_1$ và $S_2$. Little Cyan Fish sẽ cho bạn biết $\operatorname{cut}(S_1)$ nhỏ hơn, bằng hay lớn hơn $\operatorname{cut}(S_2)$.

Có lẽ bạn có thể đoán rằng phần tiếp theo sẽ nói gì đó về việc khôi phục lại đồ thị, nhưng lần này nhiệm vụ đơn giản hơn. Little Cyan Fish cho bạn một đỉnh $u$, và cậu ấy muốn bạn tìm tất cả các đỉnh kề với $u$ trong tối đa $n + 10$ truy vấn.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $u$ ($1 \le n \le 1000$, $1 \le u \le n$), lần lượt biểu thị số lượng đỉnh và đỉnh đã cho. Sau đó, quá trình tương tác bắt đầu.

Giao tiếp

Để thực hiện một truy vấn, hãy in ra một dòng theo định dạng sau:

$$?\ s_1\ s_2$$

trong đó $s_1$ và $s_2$ là các xâu có độ dài $n$, chỉ gồm các ký tự 0 và 1. Với mỗi $j \in \{1, 2\}$, đỉnh $i$ thuộc tập hợp $S_j$ khi và chỉ khi ký tự thứ $i$ của $s_j$ là 1. Các tập hợp có thể rỗng, có thể giao nhau và có thể bằng nhau.

Để phản hồi lại truy vấn, bạn sẽ nhận được một ký tự duy nhất <, =, hoặc >, lần lượt có nghĩa là $\operatorname{cut}(S_1)$ nhỏ hơn, bằng hoặc lớn hơn $\operatorname{cut}(S_2)$. Bạn phải đảm bảo rằng số lượng truy vấn bạn thực hiện không vượt quá $n + 10$.

Để báo cáo đáp án, hãy in ra một dòng theo định dạng sau:

$$!\ k\ v_1\ v_2\ \dots\ v_k$$

trong đó $k$ ($0 \le k \le n - 1$) là số lượng đỉnh kề với $u$, và $v_1, v_2, \ldots, v_k$ là các nhãn phân biệt của chúng theo thứ tự bất kỳ. Nếu $k = 0$, hãy in ra ! 0. Việc báo cáo đáp án không được tính là một truy vấn. Chương trình của bạn phải kết thúc ngay lập tức sau khi báo cáo đáp án.

Sau khi in ra một truy vấn hoặc báo cáo đáp án, đừng quên in ký tự xuống dòng và làm rỗng bộ đệm đầu ra (flush). Nếu bạn thực hiện một truy vấn không hợp lệ hoặc vượt quá giới hạn số truy vấn, trình tương tác sẽ đóng luồng dữ liệu vào và chương trình của bạn phải kết thúc ngay.

Trong bài toán này, trình tương tác là thích ứng (adaptive). Điều này có nghĩa là đồ thị có thể thay đổi tùy thuộc vào các truy vấn của bạn, miễn là nó không mâu thuẫn với bất kỳ phản hồi nào trước đó. Đáp án của bạn phải chính xác với mọi đồ thị nhất quán với tất cả các phản hồi mà bạn đã nhận được.

Ví dụ

Dữ liệu vào 1

4 1

<

=

<

=

Dữ liệu ra 1

? 0000 1000

? 0100 1100

? 0010 1010

? 0001 1001

! 2 2 4

Ghi chú

Một đồ thị nhất quán với tương tác trong ví dụ có các cạnh $(1, 2)$, $(1, 4)$ và $(2, 3)$.

Công cụ kiểm thử: Một công cụ kiểm thử được cung cấp để giúp thí sinh phát triển và kiểm tra lời giải của mình. Bạn có thể tải công cụ này từ phần tệp đính kèm. Chạy công cụ với tùy chọn -h để hiển thị hướng dẫn sử dụng. Công cụ này kiểm tra quá trình tương tác và đáp án được báo cáo, nhưng không áp đặt giới hạn thời gian hay bộ nhớ.

Công cụ kiểm thử sử dụng một đồ thị cố định được chỉ định trong tệp dữ liệu vào của nó trong suốt quá trình tương tác, trong khi trình tương tác chính thức là thích ứng. Việc vượt qua các phép thử với công cụ kiểm thử không đảm bảo rằng lời giải của bạn là chính xác khi chấm với trình tương tác chính thức.