아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

달력 조각

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

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

어려움10점 중 8점

유형
구현, 시뮬레이션, 완전 탐색, 문자열 매칭
정답자
아직 제출이 없습니다

문제

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

  • 각 달은 정확히 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이 주어진다 (2≤n,m≤102 \le n, m \le 10).

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

출력

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

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

예제2

  1. 예제 1

    입력
    2 8
    DECEMBER
    ...2..9.
    
    예상 출력
    1901
    1907
    1912
    1918
    1929
    1935
    1940
    1946
    1957
    1963
    1968
    1974
    1985
    1991
    1996
    2002
    2013
    2019
    2024
    2030
    2041
    2047
    2052
    2058
    2069
    2075
    2080
    2086
    2097
    
  2. 예제 2

    입력
    3 2
    ..
    29
    ..
    
    예상 출력
    1904
    1932
    1960
    1988
    2016
    2044
    2072