특별한 학교 탈출
면접 대비시간 제한1초메모리 제한1024 MB
N명의 교사 순찰 기록이 주어질 때, 아무 교사도 순찰하지 않는 가장 이른 교시를 구하고 없으면 ESCAPE FAILED를 출력합니다.
문제
NLCS Jeju의 학생들은 수업에 질려 학교에서 탈출하고 싶어 한다. 수업 시간에 학교를 탈출하는 것은 어려운 일이다.
NLCS Jeju의 수업 시간은 교시부터 교시까지이다. NLCS Jeju에는 명의 선생님이 있으며, 각 선생님은 정해진 스케줄에 따라 교시부터 교시 사이의 수업 시간 동안 순찰한다. 학생들은 들키지 않으려면 아무도 순찰하지 않을 때 학교를 탈출해야 한다. 탈출을 시도하는 시각에 순찰하는 선생님이 있으면 무조건 들킨다.
각 선생님의 순찰 스케줄이 주어질 때, 학생들이 학교를 탈출할 수 있는지 판단하고, 탈출할 수 있다면 가장 빠른 탈출 시각을 구하라.
입력
첫 번째 줄에 선생님의 수 과 수업 시간의 수 이 공백으로 구분되어 주어진다.
두 번째 줄부터 번째 줄까지 O와 X로 이루어진 길이 의 문자열이 주어진다. 번째 줄의 번째 문자가 O이면 번째 시각에 번째 선생님이 순찰하고, X이면 순찰하지 않는다.
출력
학생들이 선생님에게 들키지 않고 가장 빠르게 학교를 탈출했을 때의 교시를 출력하라. 들키지 않고 탈출할 수 없다면 ESCAPE FAILED를 출력하라.