Journey to Uzbekistan

You are the leader of the New Zealand IOI Team. As such, you are in charge of booking the flights to IOI 2026 in Uzbekistan. Unfortunately your WiFi is broken, but before it went down you managed to download a list of every flight you might want to take.

There are $N$ such flights. Every flight is one way and connects two airports, for example airport ABC to airport XYZ (airports are given by three letter codes) and takes exactly $h_i$ hours and $m_i$ minutes to arrive. Flights are scheduled either daily or weekly:

• If a flight is scheduled daily, you just have the time (in 24-hour format) at which it departs
• If a flight is scheduled weekly, you are given the time, as well as the day of the week at which it departs.

To make sure you have enough time to make any connecting flights, you want to ensure that you leave at least $h_c$ hours and $m_c$ minutes between the time you arrive at an airport and the time at which you will leave it.

The team will be leaving from Auckland International Airport (denoted AKL) and needs to get to Tashkent International Airport (denoted TAS) by 22:00 NZ Time (10 pm) on Sunday the 9th of August. Your goal is to find a series of flights and connections that minimises how early the team should get to Auckland airport. Specifically, find the minimum possible time between your first departure and 22:00 on Sunday the 9th of August.

Input

• The first line will contain three space-separated integers $N, h_c, h_m$ — the number of different flights, and the number of hours and minutes to wait between any two connecting flights.
• The next $N$ lines will each describe one flight each. Each line will have one of the following two forms, depending on whether the flight is scheduled daily or weekly
  • If the flight is scheduled daily, the line will have a single letter D followed by two airport codes $a_i$ and $b_i$ (denoting the origin and destination of the flight respectively), two integers $h_i$ and $m_i$ (denoting how long the flight will take) and then a single 24-hour timestamp in the form HH:MM, denoting when the flight departs.
  • If the flight is scheduled weekly, the line will have a single letter W followed by two airport codes $a_i$ and $b_i$ and two integers $h_i$ and $m_i$ as above. Then, it will have the code for the day of the week the flight is scheduled to leave (one of MON, TUE, WED, THU, FRI, SAT, SUN) followed by a 24-hour timestamp denoting the time at which the flight leaves.

Note that a pair of airports can be connected by more than one flight! However, if two flights cover the same route then it is guaranteed that they will never leave the origin airport at the exact same time. (So, for example, you cannot have a flight leaving AKL for SYD at 16:00 every day, as well as another flight leaving AKL for SYD at 16:00 every Monday).

For convenience, all time are given in New Zealand time.

To clarify the input format, please look at the sample inputs.

Output

Output the minimum possible total travel time as two positive space-separated integers $h_t$ and $m_t$, the total number of hours and minutes of travel time. Note that one must have $0 \le m_t \le 59$.

Constraints

• $1 \le N \le 2 \cdot 10^5$
• All flights are less than 24 hours. That is $0 \le h_i \le 23$ and $0 \le m_i \le 59$ for all $i$.
• All flights last at least one minute, so there is no $i$ such that $h_i = m_i = 0$
• Similarly, $0 \le h_c \le 23$ and $0 \le m_c \le 59$ and at least one of $h_c, m_c$ is non-zero. So the required waiting time between flights is less than 24 hours and at least 1 minute.
• All airport codes consist of exactly three uppercase letters A through Z.
• It is guaranteed that there is a way to get from AKL to TAS using the given flights.

Subtasks

• Subtask 1 (+14%): All flights leave from AKL and go to TAS.
• Subtask 2 (+17%): All flights leaving from the same airport go to the same airport and all flights arriving at the same airport come from the same airport. Additionally, there are no incoming flights into AKL and no outgoing flights from TAS.
• Subtask 3 (+19%): All flights are weekly, leaving every Sunday at 21:00 and with a flight duration of one hour.
• Subtask 4 (+9%): $1 \le N \le 70$
• Subtask 5 (+12%): $1 \le N \le 5000$
• Subtask 6 (+9%): All flights are daily
• Subtask 7 (+20%): No further constraints

Notes

If you are using Python and your solution is exceeding the time limit, try selecting Python 3.11 (PyPy 7.3.19) when submitting as this will generally make your code run faster.

Sample Explanations

Sample One

Here we know of three flights. To be safe we want to make sure we leave at least two hours between the time at which we land in an airport and the time at which we leave it.

The three flights are as follows:

1. There is a daily flight from AKL (Auckland) to TAS (Tashkent) leaving every day at 8:30 am and lasting 15 hours and 0 minutes
2. There is a weekly flight from AKL to TAS leaving every Saturday at 9:00 am and lasting 15 hours and 30 minutes
3. There is a daily flight from AKL to WLG (Wellington) leaving every day at noon (12:00 pm) and lasting 1 hour and 10 minutes.

The optimal solution is to take the weekly flight on Saturday the 8th of August at 9:00 am, arriving in Tashkent at 00:30 (NZ time) on the 9th of August, so we arrive in time for the event. We left exactly 37 hours before 10 pm on the 9th of August so we output 37 0, representing 37 hours and 0 minutes.

Sample Two

The optimal flight plan is:

• Take flight 2, leaving AKL on Friday the 7th of August at 9:00 am, arriving in MEL at 1:15pm (NZ Time) on the same day
• Take flight 7, leaving MEL on Friday the 7th of August at 10:10 pm (NZ Time), arriving in DBX at 12:10pm (NZ Time) on the next day
• Take flight 8, leaving DBX on Sunday the 9th of August at 5:30 am (NZ Time), arriving in TAS at 12:20 pm (NZ Time) on the same day

There are exactly 61 hours between 9 am on the 7th of August and 10 pm on the 9th of August

Sample Three

The optimal flight plan is:

• Take flight 2, leaving AKL at 1:35 am on Sunday the 9th of August, arriving in DBX at 1:35 pm on the same day.
• Take flight 1, leaving DBX at 3:10 pm on Sunday the 9th of August, arriving in TAS at 10:00pm on the same day. We have gotten to Tashkent exactly on the desired time.

There are exactly 20 hours and 25 minutes between 1:35 am on the 9th of August and 10 pm on the 9th of August.

Note that there is exactly 1 hour and 35 minutes between the moment we land at DBX and the moment we leave it for TAS. This is exactly the minimum time between connections as specified in the first line of input.

Sample Four

This case is almost identical to sample three, except that the minimum time for transit is now one minute longer, at 1 hour and 36 minutes, so the solution from before is no longer valid! A possible solution is now:

• Take flight 2, leaving AKL at 1:35 pm on Sunday the 2nd of August, arriving in DBX at 1:35 pm on the same day.
• One week later, take flight 1 at 3:10 pm on Sunday the 9th of August, arriving in TAS at 10:00pm on the same day.

There are exactly 188 hours and 25 minutes between 1:35 am on the 2nd of August and 10 pm on the 9th of August.