Kod

Limit pamięci: 64 MB

Bajtocki Instytut Telekomunikacyjny (BIT) zajmuje się ustalaniem standardów przesyłania danych w sieciach telekomunikacyjnych Bajtocji. Bajtazar, jeden z informatyków pracujących w BIT, zajmuje się kodami prefiksowymi - specjalnym sposobem reprezentowania znaków. Każdemu znakowi bajtockiego alfabetu odpowiada pewien ciąg bitów, nazywany kodem tego znaku. Kody znaków mają następujące własności:

• Kod żadnego znaku nie jest prefiksem (tj. początkowym fragmentem) kodu żadnego innego znaku. Na przykład, jeśli 010010 jest kodem litery A, to żaden z ciągów bitów: 0, 01, 010, 0100 ani 01001 nie może być kodem żadnego znaku. Podobnie, 0100100, 0100101 oraz dłuższe ciągi zaczynające się od 010010 nie mogą być kodami znaków.
• Jeśli dany ciąg bitów jest prefiksem kodu pewnego znaku, ale nie jest całym kodem, to ciągi bitów postaci i (czyli z dopisanym na końcu zerem lub jedynką) są prefiksami kodów (lub całymi kodami) pewnych znaków. Na przykład, jeśli 0100 jest prefiksem kodu litery A, to 01000 oraz 01001 muszą być prefiksami kodów (lub kodami) pewnych znaków.

Rozważmy następujący, przykładowy kod prefiksowy dla alfabetu złożonego ze znaków A, B, C, D i E:

znak	kod znaku
A	00
B	10
C	11
D	010
E	011

Kodowanie ciągu znaków za pomocą kodu prefiksowego polega na połączeniu kodów jego kolejnych znaków. Na przykład zakodowany ciąg BACAEBABAE ma postać 1000110001110001000011.

Bajtazar zauważył, że jeśli pewna liczba początkowych bitów zostanie utracona, to zakodowana informacja może być odkodowana niepoprawnie albo wcale. Na przykład, jeśli usuniemy pięć pierwszych bitów z ciągu podanego powyżej, to powstały ciąg 10001110001000011 zostanie odkodowany jako BACBABAE. Pięć ostatnich liter (BABAE) jest poprawnych, jednak trzy pierwsze (BAC) nie. Bajtazar zauważył, że wszystkie litery po pierwszym E zostały odkodowane poprawnie. Doszedł do wniosku, że zawsze, jeśli żadne bity kodu E nie zostaną utracone, to wszystkie kolejne znaki za E zostaną odkodowane poprawnie. Tak będzie dla dowolnego kodowanego ciągu znaków, w którym występuje E. Zauważył on też, że litera D też ma tę własność, ale litery A, B i C tej własności nie mają.

Opisaną własność kodów znaków E i D Bajtazar określił jako bycie kodem synchronizującym. Bajtazar powierzył Ci zadanie napisania programu znajdującego, dla danego kodu prefiksowego, wszystkich kodów synchronizujących. Aby zaoszczędzić czas, wymyślił sobie, że pokaże Ci wszystkie kody znaków na swoim binarnym monitorze. Monitor ma cztery przyciski:

• 0 - dopisz
• 1 - dopisz
• B - backspace, usuwa ostatnio dopisaną cyfrę
• X - po naciśnięciu tego przycisku monitor wydaje charakterystyczny dźwięk "beep".

Na początku wyświetlacz jest pusty; Bajtazar kolejno naciska przyciski i gdy na monitorze pojawia się kod kolejnego znaku, Bajtazar naciska przycisk X. Po pokazaniu ostatniego znaku Bajtazar czyści ekran (naciskając odpowiednią liczbę razy przycisk B). Wiesz, że Bajtazar pokaże Ci cały kod prefiksowy, naciskając najmniejszą możliwą dla tego kodu liczbę przycisków.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę przycisków naciśniętych przez Bajtazara. W kolejnym wierszu znajduje się -literowy napis złożony ze znaków '0', '1', 'B' oraz 'X', oznaczających poszczególne przyciski. Każde naciśnięcie przycisku X oznacza kolejny znak (znaki numerujemy od 1). Suma długości wszystkich kodów nie przekroczy .

Wyjście

W pierwszym wierszu standardowego wyjścia należy wypisać liczbę - liczbę kodów synchronizujących. W kolejnych wierszach należy wypisać, w porządku rosnącym, numery znaków, które są kodami synchronizującymi, po jednym w wierszu. Jeżeli dla danego kodu prefiksowego nie ma żadnych kodów synchronizujących, to należy wypisać tylko jeden wiersz zawierający liczbę 0.

Przykład

Dla danych wejściowych:

21
11XB0XBB00XB11XB0XBBB

poprawną odpowiedzią jest:

2
4
5

Wyjaśnienie przykładu

Oto kolejne kody, które pojawiają się na monitorze Bajtazara: 11, 10, 00, 011, 010. Kody 011 i 010 są kodami synchronizującymi.

Autor zadania: Marek Biskup.