한 번만 권하는 배식대

문제

어느 학교의 급식실에서는 학생마다 원하는 반찬을 미리 조사한다. 오늘 준비한 반찬은 0번과 1번 두 종류이며, 학생은 자신이 신청한 종류의 반찬만 받는다. 학생 N명은 1번부터 N번까지 번호가 붙어 있고, 처음에는 번호가 작은 학생부터 차례대로 한 줄로 서 있다. 각 학생이 신청한 반찬의 종류는 배식이 끝날 때까지 바뀌지 않는다. 배식대에는 반찬이 담긴 접시 M개가 정해진 순서로 도착한다. 접시 하나에는 한 종류의 반찬만 담겨 있다. 담당자는 접시가 도착할 때마다 다음 규칙에 따라 정확히 한 번 처리한다. 줄에 학생이 있다면 맨 앞 학생에게만 그 접시를 권한다. 접시의 반찬이 그 학생이 신청한 종류와 같으면, 학생은 접시를 받고 줄에서 완전히 빠진다. 종류가 다르면 학생은 접시를 받지 않고 줄의 맨 뒤로 이동한다. 이때 거절된 접시는 다른 학생에게 다시 권하지 않고 바로 회수한다. 줄에 학생이 한 명뿐이어도 같은 규칙을 적용한다. 그 학생이 접시를 거절하면 줄에는 여전히 그 학생 한 명이 남는다. 접시가 도착했을 때 줄이 비어 있다면 해당 접시는 바로 회수한다. 학생이 접시를 받거나 맨 뒤로 이동하는 처리를 마친 뒤에 다음 접시를 처리하며, 처리 도중 새 학생이 들어오거나 접시의 순서가 바뀌는 일은 없다. 급식실에서는 모든 접시를 처리한 뒤의 배식 기록을 확인하려 한다. 접시를 받은 학생 수와 회수한 접시 수를 구하고, 아직 줄에 남아 있는 학생의 번호를 맨 앞부터 순서대로 출력하는 프로그램을 작성한다. 학생 한 명은 접시를 최대 한 개만 받으며, 도착한 모든 접시는 학생에게 전달되거나 회수되는 두 경우 중 하나로 처리된다.

입력

첫째 줄에 학생 수 N과 접시 수 M이 공백으로 구분되어 주어진다. N과 M은 정수이며 1 ≤ N, M ≤ 100,000이다.
둘째 줄에 길이가 N인 문자열 A가 주어진다. A의 i번째 문자는 i번 학생이 신청한 반찬의 종류이다.
셋째 줄에 길이가 M인 문자열 B가 주어진다. B의 j번째 문자는 j번째로 도착하는 접시에 담긴 반찬의 종류이다.
A와 B는 문자 0과 1로만 이루어지며 문자열 내부에는 공백이 없다.

출력

첫째 줄에 접시를 받은 학생 수와 회수한 접시 수를 공백으로 구분하여 출력한다. 둘째 줄에 줄에 남은 학생의 번호를 맨 앞부터 순서대로 공백으로 구분하여 출력한다. 남은 학생이 없으면 둘째 줄에 0 하나를 출력한다.

5 7
01010
1100101

4 3
5

2 5
00
01000

2 3
0

3 2
111
00

0 2
3 1 2

출처: Devin.KR 자체 제작