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

เกมนี้เล่นบนกระดานที่เริ่มต้นด้วยความว่างเปล่า มีความกว้าง $10$ และมีความสูงไม่จำกัด ชิ้นส่วนบล็อกจะตกลงมาจากด้านบนทีละชิ้น ตามลำดับที่ระบุไว้ในข้อมูลนำเข้าทุกประการ

มีชิ้นส่วนเพียงสองประเภทเท่านั้น:

• ชิ้นส่วน I มีรูปร่างเหมือนแท่งแนวตั้งที่มีความสูง $4$ และความกว้าง $1$
• ชิ้นส่วน O มีรูปร่างเหมือนสี่เหลี่ยมจัตุรัสทึบที่มีความสูง $2$ และความกว้าง $2$

เมื่อชิ้นส่วนปรากฏขึ้น Franek จะต้องเลือกตำแหน่งที่จะปล่อยมันลงไป:

• ชิ้นส่วน I สามารถปล่อยลงในคอลัมน์ใดก็ได้จากทั้ง $10$ คอลัมน์
• ชิ้นส่วน O สามารถปล่อยลงโดยให้ทั้งสองคอลัมน์ของมันอยู่ภายในกระดานทั้งหมด (กล่าวคือ เริ่มต้นที่คอลัมน์ใดก็ได้ตั้งแต่ $1$ ถึง $9$)

เมื่อชิ้นส่วนเริ่มตกลงมา มันจะเคลื่อนที่ลงในแนวดิ่งจนกว่าจะตกลงบนบล็อกที่มีอยู่แล้วหรือตกลงที่ก้นกระดาน ชิ้นส่วนไม่สามารถหมุน เลื่อนไปด้านข้างกลางอากาศ หรือแยกออกเป็นส่วนๆ ได้ หลังจากที่ชิ้นส่วนลงจอดแล้ว ช่องทั้งหมดที่มันทับอยู่จะถูกเติมเต็ม

เมื่อใดก็ตามที่แถวแนวนอนของกระดานถูกเติมเต็มด้วยบล็อกจนครบ (หมายความว่าทั้ง $10$ คอลัมน์มีบล็อกอยู่ที่ความสูงนั้น) แถวนั้นจะหายไป บล็อกทั้งหมดที่อยู่เหนือแถวนั้นจะเลื่อนลงมาหนึ่งหน่วย หากมีหลายแถวที่ถูกเติมเต็มในเวลาเดียวกัน แถวเหล่านั้นทั้งหมดก็จะหายไปพร้อมกัน

คุณจะได้คะแนนหนึ่ง tetris เมื่อใดก็ตามที่มี สี่แถวหายไปพร้อมกันพอดี เป้าหมายของเกมคือการทำคะแนน tetris ให้ได้มากที่สุดเท่าที่จะเป็นไปได้

กระดานแรกแสดงตัวอย่างการจัดวางของชิ้นส่วน หลังจากปล่อยชิ้นส่วน I ลงในคอลัมน์ที่ $8$ มันก็เริ่มตกลงมาดังที่แสดงในกระดานที่สองและสาม หลังจากนั้น สี่แถวล่างสุดจะหายไป ได้คะแนนหนึ่ง tetris และส่งผลให้เป็นกระดานที่สี่

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

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

บรรทัดแรกมีจำนวนเต็มหนึ่งตัวคือ $N$ แทนจำนวนชิ้นส่วน บรรทัดที่สองมีสตริงความยาว $N$ ซึ่งประกอบด้วยอักขระ I และ O เท่านั้น อธิบายลำดับของชิ้นส่วนตั้งแต่ชิ้นแรกจนถึงชิ้นสุดท้าย

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

ในบรรทัดแรก ให้ส่งออกจำนวนเต็มหนึ่งตัวซึ่งเป็นจำนวน tetris สูงสุดที่ 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

หมายเหตุ

ข้อมูลส่งออกที่แสดงเป็นเพียงหนึ่งในลำดับการปล่อยที่ถูกต้อง ลำดับอื่นๆ อาจทำจำนวน tetris สูงสุดได้เท่ากัน