만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

특별한 학교 탈출

면접 대비

시간 제한1초메모리 제한1024 MB

요약
N명의 교사 순찰 기록이 주어질 때, 아무 교사도 순찰하지 않는 가장 이른 교시를 구하고 없으면 ESCAPE FAILED를 출력합니다.
난이도

쉬움10점 중 2점

유형
구현, 문자열
정답자
아직 제출이 없습니다

문제

NLCS Jeju의 학생들은 수업에 질려 학교에서 탈출하고 싶어 한다. 수업 시간에 학교를 탈출하는 것은 어려운 일이다.

NLCS Jeju의 수업 시간은 11교시부터 MM교시까지이다. NLCS Jeju에는 NN명의 선생님이 있으며, 각 선생님은 정해진 스케줄에 따라 11교시부터 MM교시 사이의 수업 시간 동안 순찰한다. 학생들은 들키지 않으려면 아무도 순찰하지 않을 때 학교를 탈출해야 한다. 탈출을 시도하는 시각에 순찰하는 선생님이 있으면 무조건 들킨다.

각 선생님의 순찰 스케줄이 주어질 때, 학생들이 학교를 탈출할 수 있는지 판단하고, 탈출할 수 있다면 가장 빠른 탈출 시각을 구하라.

입력

첫 번째 줄에 선생님의 수 NN과 수업 시간의 수 MM이 공백으로 구분되어 주어진다.

두 번째 줄부터 N+1N+1번째 줄까지 O와 X로 이루어진 길이 MM의 문자열이 주어진다. j+1j+1번째 줄의 ii번째 문자가 O이면 ii번째 시각에 jj번째 선생님이 순찰하고, X이면 순찰하지 않는다.

출력

학생들이 선생님에게 들키지 않고 가장 빠르게 학교를 탈출했을 때의 교시를 출력하라. 들키지 않고 탈출할 수 없다면 ESCAPE FAILED를 출력하라.

제한

1≤N,M≤1001 \le N,M \le 100

예제3

  1. 예제 1

    입력
    5 5
    OXXOO
    XXXOX
    OOXXX
    OXXOO
    XOXXO
    
    예상 출력
    3
    
  2. 예제 2

    입력
    5 5
    OXXXX
    XOXXX
    XXOXX
    XXXOX
    XXXXO
    
    예상 출력
    ESCAPE FAILED
    
  3. 예제 3

    입력
    7 5
    OOXXO
    OXXOO
    XOXXX
    XOOOX
    OOOXX
    OXOOO
    XOOXO
    
    예상 출력
    ESCAPE FAILED