Zadanie

Homér, umelec dvojrozmerný

Počet bodov: 50, časový limit: 300ms

Homér je bytosť dvojrozmerná. Nedávno si kúpil nový mobil s dotykovým displejom a úplne ho na ňom chytila aplikácia s názvom Skicár, v ktorej je schopný maľovať obrázky.

Obrázok si môžeme predstaviť ako rad \(3n\) pixelov. V tejto demo verzii aplikácie môže mať každý pixel len jednu z dvoch farieb—bielu alebo čiernu.

Jediný spôsob, ako sa dá obrázok zmeniť, je dotknúť sa niektorého pixelu a ten zmení farbu na opačnú. Bohužiaľ, Homérov prst je široký až dva pixely, vždy teda zmení niektoré dva susedné pixely.

Homér veľmi obľubuje pestrofarebné obrázky. Konkrétne, pestrosť obrázka je v jeho mysli definovaná ako počet súvislých úsekov rovnakej farby. Napríklad 000 má pestrosť \(1\), 011110 má pestrosť \(3\), a 010101 má pestrosť \(6\).

Homér si otvoril nejaký obrázok,a chce ho spestriť tak, aby mal pestrosť aspoň \(2n\). Nechce sa pri tom ale veľmi narobiť—chce spraviť nanajvýš \(n\) dotykov.

Úloha

Dostanete popis počiatočného obrázka. Nájdite a vypíšte postupnosť dotykov, ktoré zmenia pestrosť obrázka na aspoň \(2n\).

Vstup a výstup

Na jedinom riadku vstupu sa nachádza popis obrázka dlhého \(3n\) vo forme bitového reťazca, kde \(i\)-ty bit reprezentuje farbu \(i\)-teho pixelu. Ak je \(i\)-ty bit \(0\), pixel má čiernu farbu, v opačnom prípade je bit \(1\) a pixel má bielu farbu.

Obrázok bude dlhý aspoň \(1\) a najviac \(100\,000\) pixelov.

Na výstup vypíšte v prvom riadku počet dotykov \(k \leq n\), ktoré má Homér vykonať. Na druhom riadku vypíšte \(k\) čísel \(a_1, \ldots, a_k\) reprezentujúce jednotlivé dotyky. Každý dotyk nech je popísaný pozíciou ľavého pixela, ktorého sa dotkne (a stlačí teda pixely na pozíciách \(a_i\) a \(a_i+1\)). Musí platiť \(1 \leq a_i < 3n\) (zdôrazňujeme, že dotknúť sa len samotného posledného pixelu sa nedá).

Je zaručené, že existuje aspoň jedno riešenie. Ak existuje viacero riešení, vypísať smiete ľubovoľné z nich.

Príklad

Input:

000000000

Output:

3
2 5 6

Obrázok bude vyzerať po jednotlivých dotykoch nasledovne:

011000000

011011000

011010100

Input:

111001000111

Output:

2
3 9

Input:

010101

Output:

0

Homér nemusí stlačiť nič, obrázok už je pestrý. Ak by sa nudil, mohol by kľudne prvý pixel dva krát stlačiť – nič by tým nepokazil.