Chú lùn Franek luôn yêu thích đủ mọi thể loại trò chơi. Một ngày nọ, khi đang lục lọi đồ đạc của cha mình trên gác mái, cậu tìm thấy một chiếc máy chơi game cũ có chứa thứ gì đó giống như trò chơi Tetris. Mặc dù trông giống trò chơi quen thuộc, nhưng một số quy tắc của nó lại khác.

Trò chơi được chơi trên một bảng ban đầu trống rỗng có chiều rộng $10$ và chiều cao không giới hạn. Các mảnh gạch rơi từ trên xuống, từng mảnh một, theo đúng thứ tự được cho trong dữ liệu vào.

Chỉ có hai loại mảnh gạch:

• Mảnh I, có hình dạng như một thanh dọc cao $4$ và rộng $1$.
• Mảnh O, có hình dạng như một hình vuông đặc cao $2$ và rộng $2$.

Khi một mảnh gạch xuất hiện, Franek phải chọn vị trí để thả nó xuống:

• Một mảnh I có thể được thả vào bất kỳ cột nào trong số $10$ cột.
• Một mảnh O có thể được thả sao cho hai cột của nó nằm hoàn toàn trong bảng (tức là bắt đầu tại bất kỳ cột nào từ $1$ đến $9$).

Một khi mảnh gạch bắt đầu rơi, nó sẽ hạ xuống theo phương thẳng đứng cho đến khi đáp xuống trên các khối gạch hiện có hoặc chạm đáy bảng. Các mảnh gạch không thể xoay, di chuyển sang ngang giữa không trung, hoặc tách thành nhiều phần. Sau khi mảnh gạch đáp xuống, tất cả các ô mà nó che phủ sẽ được lấp đầy.

Bất cứ khi nào một hàng ngang của bảng được lấp đầy hoàn toàn bởi các khối gạch (nghĩa là cả $10$ cột đều có một khối gạch ở độ cao đó), hàng đó sẽ biến mất. Tất cả các khối gạch phía trên nó sẽ dịch chuyển xuống dưới một đơn vị. Nếu nhiều hàng được hoàn thành cùng một lúc, tất cả chúng sẽ biến mất cùng nhau.

Bạn ghi được một điểm tetris bất cứ khi nào có đúng bốn hàng biến mất đồng thời. Mục tiêu của trò chơi là ghi được càng nhiều tetris càng tốt.

Bảng đầu tiên hiển thị một cấu hình mẫu của các mảnh gạch. Sau khi thả một mảnh I vào cột thứ $8$, nó bắt đầu rơi như minh họa ở bảng thứ hai và thứ ba. Sau đó, bốn hàng dưới cùng biến mất, ghi được một tetris, và tạo ra bảng thứ tư.

Là một chú lùn nhỏ giàu tính cạnh tranh, Franek muốn đạt được điểm số tối đa! Tuy nhiên, cậu chơi chưa đủ giỏi, vì vậy bạn phải giúp cậu ấy. Biết trước thứ tự các mảnh gạch, hãy giúp Franek xác định số lượng tetris tối đa mà cậu có thể đạt được nếu chơi một cách tối ưu. Ngoài ra, hãy cung cấp một dãy các nước đi đạt được số điểm này.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $N$, số lượng mảnh gạch. Dòng thứ hai chứa một xâu độ dài $N$, chỉ gồm các ký tự I và O, mô tả dãy các mảnh gạch từ đầu đến cuối.

Kết quả

Trên dòng đầu tiên, in ra một số nguyên duy nhất là số lượng tetris tối đa mà Franek có thể đạt được. Trên dòng thứ hai, in ra một dãy gồm $N$ số nguyên $c_1, c_2, \dots, c_N$, trong đó $c_i$ là cột mà mảnh gạch thứ $i$ cần được thả vào (đánh số từ $1$). Đối với mảnh I, $c_i$ phải thỏa mãn $1 \le c_i \le 10$. Đối với mảnh O, $c_i$ chỉ cột bên trái của nó và phải thỏa mãn $1 \le c_i \le 9$.

Nếu có nhiều dãy tối ưu, bạn có thể in ra bất kỳ dãy nào trong số đó.

Giới hạn

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

Ví dụ

Dữ liệu vào 1

10
IIOIOIOOII

Kết quả 1

1
1 2 3 5 3 6 7 7 9 10

Giải thích

Kết quả hiển thị chỉ là một dãy nước đi hợp lệ; các dãy khác cũng có thể đạt được cùng số lượng tetris tối đa.