โจทย์ข้อนี้เป็นแบบโต้ตอบ (interactive) หลังจากพิมพ์แต่ละบรรทัด คุณต้องล้างบัฟเฟอร์เอาต์พุต (flush) คุณสามารถใช้ cout << flush ใน C++, System.out.flush() ใน Java และ sys.stdout.flush() ใน Python คุณต้องปฏิบัติตามคำแนะนำในส่วนการโต้ตอบอย่างเคร่งครัด มิฉะนั้นคุณอาจได้รับผลการตรวจเช่น คำตอบผิด (Wrong Answer) เวลาเกินกำหนด (Time Limit Exceeded) หรืออื่นๆ

เนื่องจากงานในเหมืองนั้นหนักและใช้เวลานาน เหล่าคนแคระจึงตัดสินใจขอความช่วยเหลือในการทำให้งานบางส่วนเป็นอัตโนมัติ งานปัจจุบันของพวกเขาคือการจำแนกแร่ $N$ ชิ้น (ระบุด้วยหมายเลขตั้งแต่ $1$ ถึง $N$) ออกเป็นประเภทต่างๆ เพื่อช่วยในเรื่องนี้ คนแคระคนงานได้ติดตั้งสายพานลำเลียงใหม่ เหล่าคนแคระสามารถเพิ่มตัวอย่างแร่ที่จุดเริ่มต้นของสายพาน และนำออกจากปลายสายพานได้ (กล่าวคือ นำแร่ที่ถูกเพิ่มเข้าไปก่อนหน้าออก)

น่าเสียดายที่สายพานลำเลียงนี้ไม่มีฐานความรู้ จึงไม่สามารถระบุประเภทของแร่ใดๆ บนสายพานได้ อย่างไรก็ตาม มันมีคุณสมบัติที่มีประโยชน์อีกอย่างหนึ่งคือ มันจะแสดงจำนวนประเภทของแร่ที่แตกต่างกันซึ่งอยู่บนสายพานในขณะนั้น ปรากฏว่าสิ่งนี้เพียงพอสำหรับเหมืองแล้ว เนื่องจากเหล่าคนแคระไม่จำเป็นต้องทราบประเภทของแร่แต่ละชิ้น พวกเขาเพียงแค่ต้องแยกแร่ออกเป็นกองๆ ตามประเภทเดียวกันเท่านั้น

คุณสามารถช่วยเหล่าคนแคระแก้ปัญหานี้โดยใช้สายพานลำเลียงได้หรือไม่?

การโต้ตอบ

ประเภทของแร่จะถูกกำหนดไว้คงที่ตั้งแต่เริ่มต้นและไม่ขึ้นอยู่กับการสอบถามที่เกิดขึ้น

ขั้นแรก อ่านบรรทัดที่มีจำนวนเต็ม $N$ หนึ่งตัว ซึ่งแทนจำนวนแร่ที่ต้องจำแนก จากนั้นคุณสามารถดำเนินการสองประเภทต่อไปนี้:

• + id — แร่ที่มีรหัสประจำตัว id จะถูกเพิ่มเข้าไปที่จุดเริ่มต้นของสายพานลำเลียง
• - — แร่ที่ปลายสายพานลำเลียงจะถูกนำออก หากสายพานว่างเปล่า จะไม่มีอะไรเกิดขึ้น

หลังจากการดำเนินการแต่ละครั้ง สายพานลำเลียงจะส่งออกหนึ่งบรรทัดที่ระบุจำนวนประเภทที่แตกต่างกันซึ่งอยู่บนสายพานในขณะนั้น

ในการแสดงคำตอบ ขั้นแรกให้พิมพ์บรรทัดที่มี ! ตามด้วย $k$ ซึ่งเป็นจำนวนประเภทที่แตกต่างกันในเหมือง จากนั้นพิมพ์ $k$ บรรทัด แต่ละบรรทัดอธิบายหนึ่งประเภท โดยแต่ละบรรทัดต้องมีตัวเลข $c_i$ ตามด้วยรหัสประจำตัวแร่ $c_i$ ตัวของประเภทนั้น แร่ทั้ง $N$ ชิ้นจะต้องปรากฏอยู่ในหนึ่งประเภทเท่านั้น คุณสามารถแสดงประเภทและแร่ภายในแต่ละประเภทในลำดับใดก็ได้

อย่าลืม flush เอาต์พุตหลังจากการดำเนินการแต่ละครั้งและหลังจากเขียนคำตอบ อย่าลืมเว้นวรรคระหว่างตัวเลขและสัญลักษณ์ +, -, ! คุณต้องอ่านข้อมูลทั้งหมดจากตัวโต้ตอบ (interactor)

ขีดจำกัด

$1 \le N \le 500$ คุณสามารถดำเนินการได้สูงสุด $35\,000$ ครั้ง

ตัวอย่าง

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

3
1
2
2
2

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

+ 1
+ 2
+ 3
-
! 2
2 1 3
1 2

หมายเหตุ

ในการทดสอบตัวอย่างแรก $N = 3$ และประเภทของแร่ $1, 2, 3$ คือ $1, 2, 1$ ตามลำดับ

การทดสอบในเครื่อง

ในส่วน Files คุณสามารถพบไฟล์ A.zip ซึ่งประกอบด้วยชุดทดสอบตัวอย่างและตัวตรวจ grader.cpp หากต้องการทดสอบโปรแกรมของคุณ ให้คอมไพล์โปรแกรม จากนั้นส่งชื่อชุดทดสอบและไฟล์ปฏิบัติการของคุณไปยัง ./grader ที่คอมไพล์แล้ว:

./grader [test] [executable]

ตัวอย่างเช่น: ./grader 0b.in ./abc

ตัวตรวจตัวอย่างไม่รับประกันว่าจะทำงานเหมือนกับตัวตรวจอย่างเป็นทางการทุกประการ อย่างไรก็ตาม ทั้งสองตัวไม่ได้เป็นแบบปรับเปลี่ยนตามคำถาม (adaptive)