Holidays

Residents of Flatland are passionate about holidays. They believe that any significant date deserves a celebration, so there are many public holidays in Flatland. In fact, there are so many holidays that there are no regular weekends (like Saturday and Sunday in many European countries) — the residents have enough public holidays.

Each holiday has a specific day when it should be celebrated. However, many holidays are determined by complicated rules; for example, Flatland Wolf Protection Day is held on the last full moon of the year, the International Day of SUNCs on the 42nd day of summer vacation, and Flatland Meteorologist Day on the day after the first rainy summer Thursday. (Flatland meteorologists are so tough that they can predict the date of their professional holiday a year in advance.)

With such a complex holiday system, it often happens that several holidays fall on the same day. However, Flatlanders are very systematic and cannot celebrate more than one holiday on the same day, so holidays need to be rescheduled in such cases.

Of course, holidays cannot be rescheduled arbitrarily. A holiday can be moved only if all the days between its original date and its new date are also holidays. Specifically, a holiday on day $i$ can be celebrated on day $j$ under one of the following two conditions:

• i = j,

• i \neq j, but in this case, on day $i$ and on all days between $i$ and $j$ exclusively, other holidays are celebrated (note that $i$ can be either less than or greater than $j$).

Thus, the whole year is divided into alternating blocks of working and holiday days, and rescheduling is allowed only within the same block.

Flatlanders are consistent people, and they follow the principle: "if you work — then work, if you rest — then rest." They do not like frequent changes between holidays and working days. Therefore, holidays should be rescheduled so that the average length of holiday blocks is maximal.

Today, as in the whole world, New Year is coming to Flatland. In a few hours, the President of Flatland will address the citizens. By tradition, he must announce the calendar of holidays and working days for the coming year. This schedule was supposed to be prepared by the Flatland Holiday Secretary, but unfortunately, yesterday was the Day of Civic Leaders, so the Secretary did not have time to prepare the calendar — and will not have time, as he cannot use a computer and making the calendar manually takes too much time.

Therefore, you have been asked to prepare the calendar. Write a program that, knowing how many holidays fall on each day, will reschedule them according to the rules. Note that holidays cannot be celebrated before the first day of the year, and cannot be celebrated after the last day of the year.