Problem F
Multi-Year Contest Scheduling

A well-known Canadian programming contest is always held on a Friday in October each year. We need you to help choose the dates for years $2019$, $2020$, …, $2018+Z$.

There are Fridays when we cannot schedule the contest because of conflicting events. In particular, the contest cannot be held on the Friday before Canadian Thanksgiving; that date is sacred. A list of additional “forbidden dates” is provided, but every year there is at least one Friday in October when the contest can be held.

Not all contest schedules are equally good. People tend to expect the contest to be held on or near the date it was held in the previous year. For example, they don’t like to be surprised when they expect a date in early October but the contest runs late in the month, etc. There is a yearly “surprise penalty” for holding the contest on October $X$ one year when it had been on October $Y$ the year before, namely $(X-Y)^2$, which penalizes big surprises much more than little ones.

Your goal is to find a schedule for the $Z$ years following $2018$ such that the total of the yearly surprise penalties is as small as possible.

Useful facts:

• Canadian Thanksgiving is always the second Monday in October.

• January $1$, $2019$, is a Tuesday.

• Years have $365$ days, except leap years, which have an extra day in February.

• From $2018$ until the year $2400$ (exclusive), a leap year is any year divisible by $4$ but not divisible by $100$.

• January $1$ is the $1^{\textrm{st}}$ day of the year, and October $1$ is the $274^{\textrm{th}}$ day of $2018$.

• October has $31$ days.

• The contest was held on October $12$, $2018$.

Input

• The first line of the input is the integer $Z$ $(1 \leq Z \leq 100)$, the number of years following $2018$ for which the contest is to be scheduled.

• The second line contains an integer $F$ $(0 \leq F \leq 50)$, the number of forbidden dates.

• The following $F$ lines contain the forbidden dates, one per line. Each forbidden date is represented by three space-separated numbers:

  1. The first number consists of $4$ digits and represents the year. It is between $2019$ and $2118$, inclusive.

  2. The second number is always $10$, representing October.

  3. The third number consists of two digits and represents the day in October. It ranges between $01$ and $31$, inclusive.

  The dates are given in chronologically increasing order. There is no guarantee that all forbidden dates are Fridays.

Output

The first line of the output is an integer representing the smallest total surprise penalty that any schedule can achieve. The remaining $Z$ lines contain the chosen dates of a schedule with this total surprise penalty, one date per line, in chronologically increasing order. Note that the input data is chosen so that this schedule is unique. Dates should be formatted as in the input: $4$ digits, a space, the number $10$, a space, and $2$ digits.

2
5
2019 10 18
2019 10 19
2020 10 02
2020 10 16
2020 10 23

194
2019 10 25
2020 10 30

3
6
2019 10 04
2019 10 18
2021 10 15
2021 10 22
2021 10 29
2111 10 01

475
2019 10 25
2020 10 16
2021 10 01