cho.sh

Calendar Fragment

Given a small rectangular fragment cut from a fixed-format yearly calendar, list all years from 1900 to 2100 whose calendar could contain that fragment.

Hard8ImplementationSimulationBrute forceString matchingNo attempts yetTime limit1sMemory limit512 MB

Problem

A calendar for one year fits in a single large matrix of characters. Every element of the matrix is an uppercase English letter, a digit, or a dot. The calendar is built by the following rules.

  • Each month occupies a submatrix of exactly 8 rows and 17 columns.
  • The name of the month is written in uppercase English in the first row of that submatrix, starting at its second column.
  • All days of the month are written in 6 groups that are 7 rows tall and 2 columns wide. Between two neighboring groups there is one empty column filled with dots.
  • Each group holds consecutive day numbers that belong to the same week.
  • A day number has one or two digits. A one digit number goes in the right column of its group.
  • The first of the seven rows corresponds to Monday.
  • The first group holds at least one day number, while the fifth and the sixth groups may be empty, for example when a month of 28 days starts on a Monday.
  • The twelve months are laid out in three bands separated by one empty row.
  • Each band holds four consecutive months separated by one empty column.
  • All four edges of the calendar carry an empty margin of one row or one column.

The whole calendar is therefore exactly 28 rows by 73 columns. The complete calendar for 2017 is shown below. You can read the English month names from it. A year is a leap year if it is divisible by 400, or if it is divisible by 4 and not by 100. January 1, 1900 was a Monday.

.........................................................................
..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....
.........................................................................

Archaeologists found a rectangular fragment cut out of one such calendar. They also know that the fragment was not rotated and was not changed in any other way. Find every year from 1900 to 2100 inclusive that the fragment could have been cut from.

Input

The first line holds two natural numbers nn and mm (2≤n,m≤102 \le n, m \le 10), the number of rows and the number of columns of the fragment.

Each of the next nn lines holds a string of mm characters, one row of the fragment.

Output

Print every possible year in ascending order, one per line.

The input is always such that at least one year is possible.