키 두드리기

고란은 무릎 수술에서 회복하는 동안 암호 키를 저장하는 스마트카드를 이리저리 실험하고 있다. 이 문제에서 키는 길이가 $3n$인 비트열이고, $n$은 양의 정수다. 키의 각 비트에는 왼쪽부터 $1$번부터 $3n$번까지 번호가 붙는다. 키의 무게는 값이 서로 다른 이웃한 비트 쌍의 개수에 $1$을 더한 값이다. 예를 들어 키 "000"의 무게는 $1$이고, 키 "011010100"의 무게는 $7$이다.

고란은 스마트카드 회로에 약한 전기 충격을 흘려서 키를 조작할 수 있다는 사실을 알아냈다. 정확히는 다음 연산을 원하는 만큼 확실하게 수행할 수 있다. 이웃한 두 비트를 아무렇게나 고른 다음, 두 비트를 모두 뒤집는다. 예를 들어 연산 한 번으로 키 "000"을 "110"으로 바꿀 수 있다.

길이가 $3n$인 키가 주어진다. 연산을 $n$번 이하로 사용해 무게가 $2n$ 이상인 키로 바꾸는 방법을 찾아라. 답은 항상 존재한다.

첫째 줄에 문자 "0"과 "1"로만 이루어진 문자열이 주어진다. 이 문자열이 처음 키다. 키의 길이는 $3n$이고, $n$은 $1 \le n \le 100000$인 정수다.

첫째 줄에 연산의 개수 $m$을 출력한다. $m > 0$이면 둘째 줄에 인덱스 $m$개를 연산한 순서대로, 공백 하나로 구분해 출력한다. $k$번째 수 $a_k$는 $k$번째 단계에서 뒤집는 두 비트 중 왼쪽 비트의 번호다. $m = 0$이면 첫째 줄만 출력한다.

조건을 만족하는 연산 순서는 여러 가지이므로, 이 문제는 다음 규칙이 만들어 내는 순서 하나만 정답으로 인정한다.

키를 왼쪽부터 세 비트씩 끊어 블록 $n$개로 나눈다. $k$번째 블록은 위치 $a = 3k-2$, $b = 3k-1$, $c = 3k$를 덮는다. 블록을 $k = 1$부터 $k = n$까지 차례대로 처리하며, 각 블록에서는 앞선 연산이 이미 바꿔 놓은 현재 키를 읽는다.

$k < n$인 블록에서는 쌍 $(a, b)$, $(b, c)$, $(c, c+1)$ 세 개를 본다. 다음 세 가지 행동을 적힌 순서대로 시도해서, 세 쌍 중 두 쌍 이상이 서로 다른 비트를 담게 되는 첫 번째 행동을 택한다. 아무것도 하지 않기, 인덱스 $b$에서 연산하기, 인덱스 $c$에서 연산하기.

마지막 블록 $k = n$에서는 쌍 $(a, b)$와 $(b, c)$만 본다. 두 쌍 중 하나라도 이미 서로 다른 비트를 담고 있으면 아무것도 하지 않고, 그렇지 않으면 인덱스 $b$에서 연산한다.

이 규칙은 연산을 $n$번보다 많이 쓰지 않으며, 항상 무게 $2n$ 이상에 도달한다.