โจทย์ข้อนี้เป็นโจทย์แบบโต้ตอบ (interactive problem)

Little Cyan Fish มีกราฟไม่มีทิศทางอย่างง่าย (simple undirected graph) ที่ซ่อนอยู่ซึ่งประกอบด้วยจุดยอด $n$ จุด โดยมีหมายเลขกำกับตั้งแต่ $1$ ถึง $n$ คุณทราบค่าของ $n$ แต่คุณไม่ทราบเส้นเชื่อมใด ๆ เลย Little Cyan Fish ชื่นชอบแนวคิดของคัต (cut) เป็นอย่างมาก สำหรับเซตของจุดยอด $S$ ให้ $\operatorname{cut}(S)$ แทนจำนวนเส้นเชื่อมที่มีจุดปลายอยู่ใน $S$ เพียงจุดเดียวเท่านั้น

Little Cyan Fish อนุญาตให้คุณเปรียบเทียบขนาดของคัตได้โดยการถามคำถาม ในหนึ่งคำถาม คุณเลือกเซตของจุดยอดสองเซตคือ $S_1$ และ $S_2$ แล้ว Little Cyan Fish จะบอกคุณว่า $\operatorname{cut}(S_1)$ น้อยกว่า เท่ากับ หรือมากกว่า $\operatorname{cut}(S_2)$

คุณอาจจะเดาได้ว่าเนื้อหาถัดไปคงจะเกี่ยวกับการกู้คืนกราฟทั้งใบ แต่คราวนี้งานของเราง่ายกว่านั้น Little Cyan Fish ให้จุดยอด $u$ มาหนึ่งจุด และเขาต้องการให้คุณหาจุดยอดทั้งหมดที่อยู่ประชิดกับ $u$ โดยใช้คำถามไม่เกิน $n + 10$ ครั้ง

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มสองจำนวนคือ $n$ และ $u$ ($1 \le n \le 1000$, $1 \le u \le n$) ซึ่งแทนจำนวนจุดยอดและจุดยอดที่กำหนดให้ตามลำดับ จากนั้นการโต้ตอบจึงเริ่มต้นขึ้น

การโต้ตอบ

ในการถามคำถามหนึ่งครั้ง ให้พิมพ์บรรทัดตามรูปแบบต่อไปนี้:

$$?\ s_1\ s_2$$

โดยที่ $s_1$ และ $s_2$ เป็นสตริงความยาว $n$ ที่ประกอบด้วยอักขระ 0 และ 1 เท่านั้น สำหรับแต่ละ $j \in \{1, 2\}$ จุดยอด $i$ จะอยู่ในเซต $S_j$ ก็ต่อเมื่ออักขระตัวที่ $i$ ของ $s_j$ เป็น 1 เซตทั้งสองอาจเป็นเซตว่าง อาจซ้อนทับกัน และอาจเท่ากันก็ได้

สำหรับการตอบกลับของคำถาม คุณจะได้รับอักขระเดี่ยวหนึ่งตัวคือ <, =, หรือ > ซึ่งหมายความว่า $\operatorname{cut}(S_1)$ น้อยกว่า เท่ากับ หรือมากกว่า $\operatorname{cut}(S_2)$ ตามลำดับ คุณต้องรับประกันว่าจำนวนคำถามที่คุณถามจะต้องไม่เกิน $n + 10$ ครั้ง

ในการรายงานคำตอบ ให้พิมพ์บรรทัดตามรูปแบบต่อไปนี้:

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

โดยที่ $k$ ($0 \le k \le n - 1$) คือจำนวนจุดยอดที่อยู่ประชิดกับ $u$ และ $v_1, v_2, \ldots, v_k$ คือหมายเลขที่แตกต่างกันของจุดยอดเหล่านั้นในลำดับใดก็ได้ หาก $k = 0$ ให้พิมพ์ ! 0 การรายงานคำตอบไม่นับเป็นหนึ่งคำถาม โปรแกรมของคุณต้องหยุดทำงานทันทีหลังจากรายงานคำตอบแล้ว

หลังจากการพิมพ์คำถามหรือการรายงานคำตอบ อย่าลืมพิมพ์อักขระขึ้นบรรทัดใหม่และล้างบัฟเฟอร์ข้อมูลส่งออก (flush) หากคุณถามคำถามที่ไม่ถูกต้องหรือใช้จำนวนคำถามเกินขีดจำกัด โปรแกรมโต้ตอบ (interactor) จะปิดสตรีมข้อมูลนำเข้าและโปรแกรมของคุณต้องหยุดทำงานทันที

ในโจทย์ข้อนี้ โปรแกรมโต้ตอบเป็นแบบปรับตัวได้ (adaptive) นั่นหมายความว่ากราฟอาจเปลี่ยนแปลงไปตามคำถามของคุณ ตราบใดที่มันไม่ขัดแย้งกับคำตอบใด ๆ ก่อนหน้านี้ คำตอบของคุณจะต้องถูกต้องสำหรับทุกกราฟที่สอดคล้องกับคำตอบทั้งหมดที่คุณได้รับ

ตัวอย่าง

ข้อมูลนำเข้า 1

4 1

<

=

<

=

ข้อมูลส่งออก 1

? 0000 1000

? 0100 1100

? 0010 1010

? 0001 1001

! 2 2 4

หมายเหตุ

กราฟหนึ่งที่สอดคล้องกับการโต้ตอบในตัวอย่างมีเส้นเชื่อม $(1, 2)$, $(1, 4)$ และ $(2, 3)$

เครื่องมือทดสอบ: มีเครื่องมือทดสอบเตรียมไว้ให้เพื่อช่วยให้ผู้เข้าแข่งขันพัฒนาและทดสอบโปรแกรมของตนเอง คุณสามารถดาวน์โหลดเครื่องมือนี้ได้จากไฟล์แนบ สั่งทำงานเครื่องมือด้วยตัวเลือก -h เพื่อแสดงคำแนะนำการใช้งาน เครื่องมือนี้จะตรวจสอบการโต้ตอบและคำตอบที่รายงาน แต่จะไม่บังคับใช้ขีดจำกัดเวลาหรือหน่วยความจำ

เครื่องมือทดสอบจะใช้กราฟคงที่ที่ระบุไว้ในไฟล์ข้อมูลนำเข้าตลอดการโต้ตอบ ในขณะที่โปรแกรมโต้ตอบอย่างเป็นทางการเป็นแบบปรับตัวได้ การผ่านการทดสอบด้วยเครื่องมือทดสอบไม่ได้รับประกันว่าโปรแกรมของคุณจะถูกต้องเมื่อตรวจกับโปรแกรมโต้ตอบอย่างเป็นทางการ