لطالما أحب القزم 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

ملاحظة

الإخراج الموضح هو مجرد تسلسل واحد صالح من الحركات؛ قد تحقق تسلسلات أخرى أيضاً نفس العدد الأقصى من نقاط التتريس.