Joey is going to take a vacation in Mexico. He wants to go from Toronto Pearson International Airport
YYZ to Cancun International Airport
CUN. During the way, he may make multiple stops.
During his trip, he will pass through ~N~ airports, starting at
YYZ labelled ~1~ and ending at
CUN labelled ~N~. Joey starts at
YYZ on day ~0~ hour ~0~. There are ~24~ hours in ~1~ day.
In total, there are ~M~ regularly scheduled flights. Each flight can be described by 3 integers ~A_i, B_i, C_i~, meaning that the flight starts from airport ~A_i~ and goes to airport ~A_i + 1~, starting at hour ~B_i~ every day, and takes ~C_i~ hours to fly to the next airport. Due to slow airport security lines, Joey must wait for ~20~ minutes before getting on a flight, and ~20~ minutes after getting off a flight.
In Mexico, there is a celebration of the fire god every hour of the day. Given that he travels optimally, what is time of the earliest show that Joey can watch?
The first line will contain ~N~ ~(2 \le N \le 10^5)~, ~M~ ~(N-1 \le M \le 10^6)~.
The next ~M~ lines will contain ~A_i~ ~(1 \le A_i \le N-1)~, ~B_i~ ~(0 \le B_i \le 23)~, ~C_i~ ~(1 \le C_i \le 48)~.
It is guaranteed that it is always possible to fly to Mexico.
Print a single line:
Day D Hour H, indicating the time of the earliest show that Joey can watch.
Sample Input 1
2 1 1 1 1
Sample Output 1
Day 0 Hour 3
Sample Explanation 1
Joey arrives at airport ~2~ at
2:00, and gets off at
Sample Input 2
3 3 1 2 10 1 1 48 2 12 1
Sample Output 2
Day 1 Hour 14
Sample Explanation 2
Joey should not take the plane that takes ~48~ hours as that is too slow.
Joey should arrive at airport ~2~ at Day ~0~ Hour ~12~ using the ~10~ hour plane, but Joey misses the next flight because he must wait for ~20~ minutes to pass airport security after getting off the flight, and another ~20~ minutes to pass security before getting on his next flight.
He gets on the airplane to depart airport ~2~ on Day ~1~ Hour ~12~ and arrives at Mexico at Day ~1~ Hour ~13~. Finally gets off the plane at
13:20 and visits the show on Day ~1~ Hour ~14~.