ZOJ Problem Set - 2606
You must know that our country is well known for its strange holidays system. We celebrate anything we can, and often new public holidays are announced, though sometimes some are cancelled.
In year 3141 some archeologists have discovered the document that they consider to be the log of changes in the system of public holidays in our country from year Ys till year Yf , inclusively. Each record of the document has the form
<date-record>, removed <date-holiday>
The record of the first type means that the public holiday on <date-holiday> was announced on day <date-record>, and the record of the second type means that the public holiday on <date-holiday> was cancelled on day <date-record>.
Unfortunately, all dates of records only include day and month, but not the year. Now the archeologists wonder, what maximal number of public holidays could have been there during the years described. Your task in this problem is to answer this question and provide the version of the document with years inserted, that would guarantee this number of the holidays.
You must assume that all records in the document are in the chronological order and that there were no day when two different events took place, that is, all dates of records in the document must be different.
Note that if the holiday was announced on its own day, the year it is announced there is no public holiday on this date. Analogously, if the holiday is cancelled on its own day, there is still the holiday this year (so people do not have to go to work after listening to morning radio programs).
Also recall, that the day of February 29 exists only in leap years, that is, years that are divisible by 4, except those divisible by 100, except those divisible by 400. For example, years 1996, 2000 and 2004 are leap, while 1999 or 2100 are not.
Input contains multiple test cases. The first line of the input is a single integer T (1 <= T <= 30) which is the number of test cases. Then T test cases follow, each preceded by a single blank line.
In each case, the first line contains Ys and Yf (1800 <= Ys <= Yf <= 2200, Yf - Ys <= 100). Next line contains n - the number of records in the document (1 <= n <= 100). Next n lines contain the the document records, one on a line. See sample input for more detailed information.
You must not consider any other holidays except those explicitly specified in the document. You may assume that no holiday is removed before it is announced.
On the first line of each case print the maximal number of public holidays for the given period. After that print n lines - the version of the document with years inserted that provides the specified number of holidays. Adhere to the format of the sample output.
Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.
If it is impossible to interpret the document in the specified way, print -1 on the first and the only line of the output file.
2 1900 1999 9 January 1, added January 1 January 1, added January 7 February 29, added February 29 November 7, added November 7 November 7, removed January 7 September 1, added May 1 August 21, removed November 7 September 1, added June 12 September 1, added December 12 1900 1900 2 May 1, added May 1 April 1, removed May 1
406 January 1 1900, added January 1 January 1 1901, added January 7 February 29 1904, added February 29 November 7 1904, added November 7 November 7 1905, removed January 7 September 1 1906, added May 1 August 21 1907, removed November 7 September 1 1907, added June 12 September 1 1908, added December 12 -1
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #7