달력 조각

고정된 형식의 연간 달력에서 잘라낸 작은 사각형 조각이 주어질 때, 1900년부터 2100년까지 그 조각을 포함할 수 있는 모든 연도를 오름차순으로 출력한다.

어려움8구현시뮬레이션완전 탐색문자열 매칭아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

한 해의 달력은 큰 문자 행렬 하나에 적을 수 있다. 행렬의 각 원소는 영어 대문자, 숫자, 점 중 하나다. 달력은 다음 규칙으로 만든다.

  • 각 달은 정확히 8행 17열짜리 부분 행렬을 차지한다.
  • 달 이름은 영어 대문자로 쓰고, 부분 행렬의 첫 번째 행에서 두 번째 열부터 적는다.
  • 그 달의 모든 날짜는 높이 7행, 너비 2열인 그룹 6개에 나누어 적는다. 이웃한 두 그룹 사이에는 점으로 채운 빈 열이 하나씩 있다.
  • 각 그룹에는 같은 주에 속하는 연속된 날짜가 들어간다.
  • 날짜는 한 자리 또는 두 자리다. 한 자리면 그룹의 오른쪽 열에 적는다.
  • 일곱 행 중 첫 번째 행이 월요일에 해당한다.
  • 첫 번째 그룹에는 날짜가 적어도 하나 들어가고, 다섯 번째와 여섯 번째 그룹은 비어 있을 수 있다. 예를 들어 28일까지 있는 달이 월요일에 시작하면 그렇다.
  • 열두 달은 세 줄로 나누어 배치하고, 줄 사이에는 빈 행을 하나 둔다.
  • 한 줄에는 연속된 네 달이 들어가고, 이웃한 두 달 사이에는 빈 열을 하나 둔다.
  • 달력의 네 변에는 모두 한 행 또는 한 열짜리 빈 여백이 있다.

따라서 달력 전체는 정확히 28행 73열이다. 아래는 2017년의 완성된 달력이다. 영어 달 이름은 이 그림에서 읽을 수 있다. 어떤 해가 400으로 나누어떨어지거나, 4로 나누어떨어지면서 100으로는 나누어떨어지지 않으면 윤년이다. 1900년 1월 1일은 월요일이었다.

.........................................................................
..JANUARY...........FEBRUARY..........MARCH.............APRIL............
.....2..9.16.23.30.....6.13.20.27........6.13.20.27........3.10.17.24....
.....3.10.17.24.31.....7.14.21.28........7.14.21.28........4.11.18.25....
.....4.11.18.25.....1..8.15.22........1..8.15.22.29........5.12.19.26....
.....5.12.19.26.....2..9.16.23........2..9.16.23.30........6.13.20.27....
.....6.13.20.27.....3.10.17.24........3.10.17.24.31........7.14.21.28....
.....7.14.21.28.....4.11.18.25........4.11.18.25........1..8.15.22.29....
..1..8.15.22.29.....5.12.19.26........5.12.19.26........2..9.16.23.30....
.........................................................................
..MAY...............JUNE..............JULY..............AUGUST...........
..1..8.15.22.29........5.12.19.26........3.10.17.24.31.....7.14.21.28....
..2..9.16.23.30........6.13.20.27........4.11.18.25.....1..8.15.22.29....
..3.10.17.24.31........7.14.21.28........5.12.19.26.....2..9.16.23.30....
..4.11.18.25........1..8.15.22.29........6.13.20.27.....3.10.17.24.31....
..5.12.19.26........2..9.16.23.30........7.14.21.28.....4.11.18.25.......
..6.13.20.27........3.10.17.24........1..8.15.22.29.....5.12.19.26.......
..7.14.21.28........4.11.18.25........2..9.16.23.30.....6.13.20.27.......
.........................................................................
..SEPTEMBER.........OCTOBER...........NOVEMBER..........DECEMBER.........
.....4.11.18.25........2..9.16.23.30.....6.13.20.27........4.11.18.25....
.....5.12.19.26........3.10.17.24.31.....7.14.21.28........5.12.19.26....
.....6.13.20.27........4.11.18.25.....1..8.15.22.29........6.13.20.27....
.....7.14.21.28........5.12.19.26.....2..9.16.23.30........7.14.21.28....
..1..8.15.22.29........6.13.20.27.....3.10.17.24........1..8.15.22.29....
..2..9.16.23.30........7.14.21.28.....4.11.18.25........2..9.16.23.30....
..3.10.17.24........1..8.15.22.29.....5.12.19.26........3.10.17.24.31....
.........................................................................

고고학자들이 이런 달력 하나에서 잘라낸 직사각형 조각을 찾아냈다. 조각은 회전하지도 않았고 다른 어떤 방식으로도 바뀌지 않았다. 이 조각을 잘라낼 수 있었던 1900년부터 2100년까지의 해를 모두 구하여라.

입력

첫째 줄에 찾아낸 조각의 행 수 nn과 열 수 mm이 주어진다 (2n,m102 \le n, m \le 10).

다음 nn개의 줄에는 각각 mm개의 문자로 이루어진 문자열이 주어진다. 조각의 한 행을 나타낸다.

출력

가능한 해를 모두 오름차순으로 한 줄에 하나씩 출력한다.

입력 자료는 가능한 해가 항상 하나 이상 존재하도록 주어진다.