드워프 Franek은 언제나 온갖 종류의 게임을 좋아했습니다. 어느 날 그는 다락방에서 아버지의 물건을 뒤지다가 테트리스(Tetris) 게임처럼 보이는 것이 들어 있는 오래된 게임기를 발견했습니다. 익숙한 게임과 비슷해 보였지만, 몇 가지 규칙이 달랐습니다.
게임은 처음에 비어 있는 너비 $10$, 높이 무제한인 보드에서 진행됩니다. 블록 조각들은 입력에서 주어진 정확한 순서대로 위에서 하나씩 떨어집니다.
조각의 종류는 단 두 가지뿐입니다:
I-조각: 높이 $4$, 너비 $1$인 수직 막대 모양입니다.O-조각: 높이 $2$, 너비 $2$인 꽉 찬 정사각형 모양입니다.
조각이 나타나면 Franek은 조각을 어디에 떨어뜨릴지 선택해야 합니다:
I-조각은 $10$개의 열 중 어느 곳에나 떨어뜨릴 수 있습니다.O-조각은 두 열이 보드 안에 완전히 들어가도록 떨어뜨릴 수 있습니다(즉, $1$번 열부터 $9$번 열까지의 어느 열에서나 시작할 수 있습니다).
조각이 떨어지기 시작하면 기존 블록의 위나 보드의 바닥에 닿을 때까지 수직으로 내려갑니다. 조각은 회전시키거나, 공중에서 옆으로 이동시키거나, 여러 부분으로 쪼갤 수 없습니다. 조각이 착지한 후에는 조각이 덮고 있는 모든 칸이 채워집니다.
보드의 가로 행 하나가 블록으로 완전히 채워질 때마다(즉, 해당 높이에서 $10$개의 열 모두에 블록이 있을 때), 그 행은 사라집니다. 그 위에 있는 모든 블록은 한 칸씩 아래로 내려옵니다. 여러 행이 동시에 완성되면 모두 함께 사라집니다.
정확히 네 개의 행이 동시에 사라질 때마다 $1$ 테트리스(tetris)를 득점합니다. 게임의 목표는 가능한 한 많은 테트리스를 득점하는 것입니다.
첫 번째 보드는 조각들의 예시 배치를 보여줍니다. $8$번째 열에 I-조각을 떨어뜨린 후, 두 번째와 세 번째 보드에 나타난 것처럼 조각이 떨어지기 시작합니다. 그 후 맨 아래 네 개의 행이 사라지면서 테트리스를 득점하고, 네 번째 보드와 같은 결과가 됩니다.
승부욕이 강한 작은 드워프 Franek은 최고 점수를 달성하고 싶어 합니다! 하지만 그는 게임을 충분히 잘하지 못하기 때문에 당신이 도와주어야 합니다. 조각이 나오는 순서를 미리 알고 있을 때, Franek이 최적의 방법으로 플레이할 경우 달성할 수 있는 최대 테트리스 횟수를 구하도록 도와주세요. 또한, 이 점수를 달성하는 이동 순서를 하나 제시하세요.
입력
첫 번째 줄에는 조각의 개수를 나타내는 하나의 정수 $N$이 주어집니다. 두 번째 줄에는 문자 I와 O로만 이루어진 길이 $N$의 문자열이 주어지며, 이는 첫 번째부터 마지막까지의 조각 순서를 나타냅니다.
출력
첫 번째 줄에 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
노트
예제에 표시된 출력은 유효한 이동 순서 중 하나일 뿐이며, 다른 순서로도 동일한 최대 테트리스 횟수를 달성할 수 있습니다.