הגמד Franek תמיד אהב כל מיני משחקים. יום אחד הוא חיטט בחפצים של אביו בעליית הגג ומצא קונסולה ישנה עם מה שנראה כמו משחק טטריס (Tetris). למרות שהוא דמה למשחק המוכר, חלק מהחוקים שלו היו שונים.

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

ישנם רק שני סוגים של חלקים:

• חלק-I, שצורתו כמו מוט אנכי בגובה $4$ וברוחב $1$.
• חלק-O, שצורתו כמו ריבוע מלא בגובה $2$ וברוחב $2$.

כאשר מופיע חלק, Franek חייב לבחור היכן להפיל אותו:

• ניתן להפיל חלק-I לכל אחת מ-$10$ העמודות.
• ניתן להפיל חלק-O כך ששתי העמודות שלו ייכנסו בשלמותן בתוך הלוח (כלומר, החל מכל עמודה מ-$1$ ועד $9$).

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

בכל פעם ששורה אופקית של הלוח מתמלאת לחלוטין בבלוקים (כלומר לכל $10$ העמודות יש בלוק באותו גובה), השורה הזו נעלמת. כל הבלוקים שמעליה יורדים למטה ביחידה אחת. אם מספר שורות מושלמות באותו הזמן, כולן נעלמות יחד.

אתה צובר טטריס (tetris) אחד בכל פעם שבדיוק ארבע שורות נעלמות בו-זמנית. מטרת המשחק היא לצבור כמה שיותר טטריסים.

הלוח הראשון מציג תצורה לדוגמה של חלקים. לאחר הפלת חלק-I בעמודה ה-$8$, הוא מתחיל ליפול כפי שמוצג בלוח השני והשלישי. לאחר מכן, ארבע השורות התחתונות נעלמות, מה שמזכה בטטריס אחד ומביא ללוח הרביעי.

בהיותו גמד קטן ותחרותי, Franek רוצה להשיג את הניקוד המקסימלי! עם זאת, הוא לא מספיק טוב במשחק, ולכן עליך לעזור לו. בידיעת סדר החלקים מראש, עזור ל-Franek לקבוע את המספר המקסימלי של טטריסים שהוא יכול להשיג אם ישחק באופן אופטימלי. בנוסף, ספק סדרת מהלכים שמשיגה ניקוד זה.

קלט

השורה הראשונה מכילה מספר שלם בודד $N$, מספר החלקים. השורה השנייה מכילה מחרוזת באורך $N$, המורכבת אך ורק מהתווים I ו-O, המתארת את סדרת החלקים מהראשון ועד האחרון.

פלט

בשורה הראשונה, הדפס מספר שלם בודד שהוא המספר המקסימלי של טטריסים ש-Franek יכול להשיג. בשורה השנייה, הדפס סדרה של $N$ מספרים שלמים $c_1, c_2, \dots, c_N$, כאשר $c_i$ היא העמודה שלתוכה יש להפיל את החלק ה-$i$ (אינדקס החל מ-$1$). עבור חלק-I, על $c_i$ לקיים $1 \le c_i \le 10$. עבור חלק-O, הערך $c_i$ מתייחס לעמודה השמאלית שלו وعליו לקיים $1 \le c_i \le 9$.

אם קיימות מספר סדרות אופטימליות, ניתן להדפיס כל אחת מהן.

מגבלות

$1 \le N \le 200\,000$.

דוגמאות

קלט 1

10
IIOIOIOOII

פלט 1

1
1 2 3 5 3 6 7 7 9 10

הערה

הפלט המוצג הוא רק סדרת מהלכים חוקית אחת; סדרות אחרות עשויות גם הן להשיג את אותו מספר מקסימלי של טטריסים.