H. Optimizing Weekend Days
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

HR of Synergy plans to set two specific weekend days for employees for the period from a given starting date to an ending date. These weekend days will remain fixed throughout the specified period, and the objective is to maximize the total number of working days, excluding both public holidays and weekend days.

The dates should follow the Gregorian calendar, meaning they should align with the standard calendar system, including leap years. A leap year is defined as any year that:

  1. Is evenly divisible by 4, and
  2. Is not evenly divisible by 100, unless it is also evenly divisible by 400.

For example:

  • 2024 is a leap year (divisible by 4 but not by 100).
  • 1900 is not a leap year (divisible by 100 but not by 400).
  • 2000 is a leap year (divisible by 400).

In leap years, February has 29 days instead of the usual 28.

A working day is any day that is neither a public holiday nor a designated weekend day. The HR wants to select two specific days of the week that will serve as weekend days. Your task is to help him choose these two days such that the total number of working days is maximized.

Input

The input consists of multiple lines:

  • The first line contains an integer $$$T ~(T \le 400)$$$ — the number of test cases.

For each test case:

  1. The first line contains two dates: the starting date and the ending date, in the format 'DD-MM-YYYY'.
  2. The second line contains an integer $$$H$$$ $$$(1 \leq H \leq 1000)$$$ — the number of holidays.
  3. Each of the next $$$H $$$ lines contains a holiday date. The holiday date can be in one of the following formats:
    • 'DD-MM': This format indicates that the holiday occurs on the same date every valid year.
    • 'DD-MM-YYYY': This format indicates that the holiday occurs only in the specific year mentioned.

Each test case should be processed independently.

The sum of $$$H$$$ over all the test cases will not exceed $$$2000$$$.

All the date ranges are between '01-01-1900' and '31-12-3000', inclusive. The dates are guaranteed to be valid.

Output

For each test case, output a single line containing two space-separated, title-cased days (e.g., "Friday Saturday") representing the weekend maximizing working days. Days are: 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday'. If multiple pairs achieve this, output the lexicographically smallest (alphabetical order, comparing the first days, then the second). Note that "Saturday Friday" and "Friday Saturday" are considered different pairs.

For example:

  • "Friday Saturday" is lexicographically smaller than "Saturday Sunday".
  • "Friday Saturday" is lexicographically smaller than "Friday Sunday".
  • "Friday Saturday" is lexicographically smaller than "Saturday Friday".
Example
Input
1
10-10-2024 24-10-2024
5
05-01
11-10-2024
12-10
15-10-2024
05-01-2024
Output
Friday Saturday