부호

접두 부호(prefix code)는 어떤 문자 집합의 각 문자에 서로 다른 이진 문자열을 하나씩 대응시키며, 이 문자열을 그 문자의 부호어(code word) 라고 부릅니다. 부호어들은 다음 두 성질을 만족합니다.

• 어떤 부호어도 다른 부호어의 접두사가 아닙니다. 예를 들어 010010 이 어떤 문자의 부호어라면 0, 01, 010, 0100, 01001 중 어느 것도, 또 010010 으로 시작하는 어떤 문자열도 다른 문자의 부호어가 될 수 없습니다.
• 이진 문자열 $w$ 가 어떤 부호어의 접두사이지만 그 자체로 완성된 부호어는 아니라면, $w0$ 과 $w1$ ($w$ 뒤에 0 또는 1 을 붙인 것) 각각도 다시 어떤 부호어의 접두사이거나 완성된 부호어입니다. 예를 들어 0100 이 어떤 부호어의 접두사라면 01000 과 01001 각각도 어떤 부호어의 접두사이거나 완성된 부호어입니다.

즉, 부호어들은 모든 내부 노드가 정확히 두 개의 자식을 갖는 완전 이진 트리의 잎에 해당합니다.

다음은 문자 집합 {A, B, C, D, E} 에 대한 접두 부호의 예입니다.

메시지는 각 문자의 부호어를 순서대로 이어 붙여 부호화합니다. 예를 들어 BACAEBABAE 는 1000110001110001000011 로 부호화됩니다.

부호화된 메시지의 앞부분 비트 몇 개가 사라지면, 메시지가 잘못 해독되거나 아예 해독되지 않을 수 있습니다. 예를 들어 위 메시지에서 앞의 다섯 비트를 지우면 10001110001000011 이 남고, 이는 BACBABAE 로 해독됩니다. 마지막 다섯 글자(BABAE)는 올바르지만 앞의 세 글자(BAC)는 틀립니다. 첫 번째 E 이후의 모든 글자는 올바르게 해독된다는 점에 주목하세요. 실제로 E 의 부호어가 온전히 읽히고 나면, 앞에서 어떤 비트가 사라졌든 그 뒤의 모든 글자는 올바르게 해독됩니다. D 의 부호어도 같은 성질을 갖지만 A, B, C 의 부호어는 그렇지 않습니다.

이런 성질을 가진 부호어를 동기화 부호어(synchronizing code word) 라고 부릅니다. 해독기가 이 부호어를 온전하고 정확하게 읽고 나면, 앞에서 어떤 비트가 사라졌든 그 뒤의 모든 글자가 올바르게 해독됩니다. 주어진 접두 부호의 모든 동기화 부호어를 찾는 것이 목표입니다.

부호어들은 버튼이 네 개인 장치로 제시됩니다.

• 0 - 화면에 비트 0 을 덧붙입니다.
• 1 - 화면에 비트 1 을 덧붙입니다.
• B - 백스페이스: 화면의 마지막 비트를 지웁니다.
• X - 삐 소리: 지금 화면에 완성된 부호어가 표시되어 있음을 알립니다.

화면은 비어 있는 상태에서 시작합니다. 각 부호어는 화면에 나타날 때까지 버튼을 누른 뒤 X 를 눌러 입력합니다. 부호어에는 X 가 눌린 순서대로 $1, 2, 3, \dots$ 의 번호를 매깁니다. 마지막 부호어 뒤에는 필요한 만큼 B 를 눌러 화면을 지웁니다.

첫째 줄에 정수 $n$ ($6 \le n \le 3\,000\,000$), 즉 누른 버튼의 개수가 주어집니다. 둘째 줄에는 0, 1, B, X 로 이루어진 길이 $n$ 의 문자열이 주어지며, 버튼을 누른 순서를 나타냅니다. X 를 누를 때마다 부호어 하나가 완성되고, 부호어의 번호는 $1$ 부터 시작합니다. 모든 부호어 길이의 합은 $10^8$ 을 넘지 않습니다.

첫째 줄에 동기화 부호어의 개수 $k$ 를 출력합니다. 이어서 동기화 부호어들의 번호를 증가하는 순서로 한 줄에 하나씩 출력합니다. 동기화 부호어가 하나도 없다면 첫째 줄에 $0$ 만 출력합니다.

예제 입력에서 버튼들은 다섯 개의 부호어 11, 10, 00, 011, 010 을 순서대로 입력합니다. 이 중 011(4번 부호어)과 010(5번 부호어)이 동기화 부호어이므로, 답으로 4 와 5 를 출력합니다.