문제

오늘은 대구과학고등학교의 권위 있는 과학 연구 대회인 '사이언키피아' 최종 보고서 제출 마감일이다. 우진이는 지난 수개월간 밤을 지새우며 공들여 보고서를 작성하고 있었다. 하지만 우진이의 강력한 라이벌인 주원이는 경쟁자를 제거하기 위해 사악한 계획을 세웠다.

우진이가 잠시 화장실에 간 사이, 주원이는 몰래 우진이의 컴퓨터를 조작하여 공들여 작성한 보고서 파일의 비트열을 엉망으로 만들어 버렸다. 주원이는 우진이의 제출을 확실하게 망치기 위해, 원본 보고서의 비트 중 최소 한 곳 이상을 반드시 변조해 두었다.

다행히 컴퓨터의 자동 저장 기능 덕분에 파일이 완전히 삭제되지는 않았으나, 복구된 파일은 비트열의 일부가 변조된 상태였다. 현재 우진이가 보유한 파일은 길이가 $N$인 비트열 $X$이며, 우진이가 원래 제출하려고 했던 원본 보고서는 길이가 $N$인 비트열 $Y$이다. 주원이의 집요한 방해 공작으로 인해, 조작된 비트열 $X$는 원본 비트열 $Y$와 항상 한 글자 이상 다른 상태로 주어진다.

절망하던 우진이를 위해 정보과학부의 윤수진 선생님께서는 길이가 $M$인 '복구 키' 비트열 $Z$를 건네주셨다. 복구 연산의 규칙은 다음과 같다.

양의 정수 $i$ ($1 \le i \le N - M + 1$)를 하나 선택하여, 현재 파일 $X$의 $i$번째 비트부터 시작하는 길이 $M$의 부분 비트열에 복구 키 $Z$로 비트별 배타적 논리합(bitwise XOR) 연산을 수행한다.

위 연산의 구체적인 동작은 다음과 같다. $1 \le j \le M$인 모든 정수 $j$에 대하여, 복구 키 $Z$의 $j$번째 비트가 $1$이라면 $X$의 $i+j-1$번째 비트가 반전된다($0$은 $1$로, $1$은 $0$으로 바뀐다). 반대로 $Z$의 $j$번째 비트가 $0$이라면 해당 위치의 비트는 변하지 않고 유지된다.

이 연산을 반복하여 서버에 저장된 비트열 $X$를 원본 비트열 $Y$와 완전히 동일하게 만들어야 한다. 연산을 한 번 수행할 때마다 상당한 시간이 소요되므로, 우진이는 최소한의 연산 횟수로 복구를 완료하여 마감 시간 안에 제출하고자 한다.

우진이는 과연 무사히 보고서 복구를 마치고 사이언키피아에서 1등을 차지할 수 있을까?

입력

첫째 줄에 파일의 길이 $N$과 복구 키의 길이 $M$이 공백으로 구분되어 주어진다. ($1 \le M \le N \le 2,000$)

둘째 줄에 주원이에 의해 조작된 파일의 상태를 나타내는 길이 $N$의 비트열 $X$가 주어진다.

셋째 줄에 우진이가 원래 제출하려 했던 원본 보고서의 상태를 나타내는 길이 $N$의 비트열 $Y$가 주어진다.

$X$와 $Y$는 항상 서로 다른 비트열임이 보장된다.

넷째 줄에 윤수진 선생님께 받은 복구 키를 나타내는 길이 $M$의 비트열 $Z$가 주어진다.

모든 비트열은 0과 1로만 이루어져 있다.

출력

만약 어떤 방법을 사용해도 $X$를 원본 상태 $Y$로 복구할 수 없다면 첫째 줄에 $-1$을 출력한다.

복구가 가능하다면:

• 첫째 줄에 파일 $X$를 $Y$로 복구하기 위해 필요한 최소 연산 횟수 $K$를 출력한다.
• 둘째 줄에 연산을 적용한 시작 위치 $i$를 나타내는 $K$개의 정수를 공백으로 구분하여 출력한다. ($1 \le i \le N - M + 1$)

최소 연산 횟수를 만족하는 방법이 여러 가지라면 그중 아무거나 하나를 출력한다.

예제 입력 1

6 3
000000
100111
101

예제 출력 1

3
1 3 4

노트

복구 키 $Z = 101$을 사용하여 $X = 000000$을 $Y = 100111$로 만드는 과정은 다음과 같다.

1. $i=1$ 선택: $X$의 1번째 비트부터 3번째 비트까지 $101$과 XOR 연산한다.
   • $000 \oplus 101 = 101$
   • 현재 $X$: 101000
2. $i=3$ 선택: $X$의 3번째 비트부터 5번째 비트까지 $101$과 XOR 연산한다.
   • $100 \oplus 101 = 001$
   • 현재 $X$: 100010
3. $i=4$ 선택: $X$의 4번째 비트부터 6번째 비트까지 $101$과 XOR 연산한다.
   • $010 \oplus 101 = 111$
   • 현재 $X$: 100111 ($Y$와 일치)

총 3번의 연산으로 복구가 가능하며, 이보다 적은 횟수로 복구하는 방법은 존재하지 않는다.