시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 5 2 2 40.000%

문제

상근이의 집에는 전구가 L개 있다. 각 전구를 켜고 끌 수 있는 스위치는 일렬로 늘어서있다. 전구가 켜진 상태에서 스위치를 누르면 꺼지고, 꺼진 상태에서 누르면 켜진다.

매일 밤, 잠을 자기 전에 상근이는 전구를 모두 끈다. 모든 스위치를 한 번씩 눌러 전구를 끄는 일은 시간이 오래걸린다.

불을 켜고 끄는 일을 조금 더 편하게 하기 위해 상근이는 스위치를 편하게 누를 수 있는 장치를 발명했다. 장치는 T개의 슬롯이 일렬로 놓여져있다. 일부 슬롯에는 스위치 버튼을 누를 수 있는 막대가 꽂혀있고, 나머지 슬롯은 비어있다. 예를 들어, 장치에 슬롯이 4개 있고, 1, 2, 4번째 슬롯에 막대가 꽂혀있으면, 이를 '1101'로 표현할 수 있다.

위의 장치로 L개의 스위치 중 가장 왼쪽 스위치를 누르면, 1, 2, 4번 스위치를 누를 수 있고, 그 전구의 상태가 변하게 된다. 3번 슬롯은 비어있기 때문에, 3번 전구는 변하지 않는다. 즉, 가장 왼쪽에 있는 슬롯을 기준으로 i번째 스위치를 누른다면 i, i+1, ..., i+T-1번째 스위치 중 막대가 꽂힌 슬롯에 대응되는 스위치의 전구가 변하게 된다. 단, T개의 모든 슬롯이 스위치와 대응되어야 한다. 즉, 스위치 바깥으로 슬롯이 나가면 안된다.

현재 스위치의 상태와 상근이가 발명한 슬롯의 상태가 주어졌을 때, 불이 켜진 상태를 최소로 하려면 장치로 슬롯을 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 L (3 ≤ L ≤ 50)과 T (1 ≤ T ≤ 7)가 주어진다. 다음 줄에 길이가 L인 문자열이 주어진다. 1은 i번째 전구가 켜진 상태, 0은 꺼진 상태이다. 세 번째 줄에는 길이가 T인 문자열이 주어진다. 0은 빈 슬롯, 1은 막대가 꽂힌 슬롯이다.

출력

첫째 줄에 최소의 불이 켜진 상태를 만들기 위해 슬롯으로 눌러야할 등불 순서의 개수 K를 출력한다. 그 다음 K줄에는 눌러야 하는 스위치를 순서대로 출력한다. 슬롯으로 누르는 가장 왼쪽 스위치의 번호를 출력한다. (장치를 회전시킬 수는 없다) K는 1000보다 작거나 같아야 한다.

예제 입력

10 4
1111111111
1101

예제 출력

5
3
1
4
7
6

힌트

1111111111  초기 상태
1100101111  3∼6번 불을 슬롯으로 누른 후
0001101111  1∼4번 불을 슬롯으로 누른 후
0000000111  4∼7번 불을 슬롯으로 누른 후
0000001010  7∼10번 불을 슬롯으로 누른 후
0000010000  6∼9번 불을 슬롯으로 누른 후

최종 1개의 불이 켜진 상태가 되고 모든 불을 끄는 해는 존재하지 않는다.