Kurcaci Franek selalu menyukai segala jenis permainan. Suatu hari ia sedang membongkar barang-barang ayahnya di loteng dan menemukan sebuah konsol tua dengan permainan yang tampak seperti Tetris. Meskipun menyerupai permainan yang sudah dikenal, beberapa aturannya berbeda.

Permainan ini dimainkan pada papan yang awalnya kosong dengan lebar $10$ dan tinggi tak terbatas. Bidak-bidak jatuh dari atas, satu per satu, tepat sesuai urutan yang diberikan dalam masukan.

Hanya ada dua jenis bidak:

• Bidak-I, berbentuk seperti batang vertikal dengan tinggi $4$ dan lebar $1$.
• Bidak-O, berbentuk seperti persegi padat dengan tinggi $2$ dan lebar $2$.

Ketika sebuah bidak muncul, Franek harus memilih di mana akan menjatuhkannya:

• Sebuah bidak-I dapat dijatuhkan ke salah satu dari $10$ kolom mana pun.
• Sebuah bidak-O dapat dijatuhkan sedemikian sehingga kedua kolomnya muat seluruhnya di dalam papan (yaitu, dimulai pada kolom mana pun dari $1$ hingga $9$).

Begitu sebuah bidak mulai jatuh, ia turun secara vertikal hingga mendarat di atas balok yang sudah ada atau di dasar papan. Bidak tidak dapat diputar, digeser ke samping di udara, atau dipecah menjadi beberapa bagian. Setelah bidak mendarat, semua sel yang ditutupinya menjadi terisi.

Setiap kali satu baris horizontal papan terisi penuh dengan balok (artinya ke-$10$ kolom memiliki balok pada ketinggian tersebut), baris tersebut menghilang. Semua balok di atasnya turun satu satuan. Jika beberapa baris selesai pada saat yang sama, semuanya menghilang bersama-sama.

Anda mencetak satu skor tetris setiap kali tepat empat baris menghilang secara bersamaan. Tujuan dari permainan ini adalah mencetak tetris sebanyak mungkin.

Papan pertama menunjukkan contoh konfigurasi bidak. Setelah menjatuhkan sebuah bidak-I di kolom ke-$8$, bidak tersebut mulai jatuh seperti yang ditunjukkan pada papan kedua dan ketiga. Setelah itu, empat baris terbawah menghilang, mencetak satu tetris, dan menghasilkan papan keempat.

Sebagai kurcaci kecil yang kompetitif, Franek ingin mencapai skor maksimum! Namun, ia kurang mahir dalam permainan tersebut, sehingga Anda harus membantunya. Dengan mengetahui urutan bidak sebelumnya, bantulah Franek menentukan jumlah maksimum tetris yang dapat ia capai jika ia bermain secara optimal. Selain itu, berikan urutan langkah yang mencapai skor ini.

Masukan

Baris pertama berisi satu bilangan bulat $N$, jumlah bidak. Baris kedua berisi sebuah string dengan panjang $N$, yang hanya terdiri dari karakter I dan O, yang menjelaskan urutan bidak dari pertama hingga terakhir.

Keluaran

Pada baris pertama, keluarkan satu bilangan bulat yang merupakan jumlah maksimum tetris yang dapat dicapai Franek. Pada baris kedua, keluarkan barisan $N$ bilangan bulat $c_1, c_2, \dots, c_N$, di mana $c_i$ adalah kolom tempat bidak ke-$i$ harus dijatuhkan (indeks dimulai dari $1$). Untuk bidak-I, $c_i$ harus memenuhi $1 \le c_i \le 10$. Untuk bidak-O, $c_i$ mengacu pada kolom kirinya dan harus memenuhi $1 \le c_i \le 9$.

Jika terdapat beberapa barisan optimal, Anda dapat mengeluarkan yang mana saja di antaranya.

Batasan

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

Contoh

Masukan 1

10
IIOIOIOOII

Keluaran 1

1
1 2 3 5 3 6 7 7 9 10

Catatan

Keluaran yang ditampilkan hanyalah salah satu barisan langkah yang valid; barisan lain mungkin juga mencapai jumlah maksimum tetris yang sama.