هذه المسألة تفاعلية. بعد طباعة كل سطر، يجب عليك تفريغ مخزن الإخراج المؤقت (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) بعد كل عملية وبعد كتابة الإجابة. تذكر وضع مسافات بين الأرقام والرموز + و - و !. يجب عليك قراءة جميع البيانات من المتفاعل.

القيود

$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. لاختبار حلك، قم بترجمته برمجياً (compile)، ثم مرر اسم الاختبار والملف التنفيذي الخاص بك إلى ./grader المترجم:

./grader [test] [executable]

على سبيل المثال: ./grader 0b.in ./abc

لا يُضمن أن يتصرف مصحح المثال بشكل مطابق للمصحح الرسمي. ومع ذلك، فإن كليهما غير تكيفي (non-adaptive).