משימה זו היא אינטראקטיבית. לאחר הדפסת כל שורה, עליך לרוקן את חוצץ הפלט (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. כדי לבדוק את הפתרון שלך, קמפל אותו, ולאחר מכן העבר את שם המבחן ואת קובץ ההרצה שלך אל ה-./grader המקומפל:

./grader [test] [executable]

לדוגמה: ./grader 0b.in ./abc

לא מובטח שהבודק לדוגמה יתנהג באופן זהה לבודק הרשמי. עם זאת, אף אחד מהם אינו אדפטיבי.