Under construction

Still being built. Things may change

Among the many YouTubers, virtual YouTubers exist

Interview

Time limit1sMemory limit1024 MB

Summary
Given broadcast logs, find the YouTubers who have 5 broadcasts in some Sunday-to-Saturday week with 60 hours or more of total live time.
Level

Easy3 of 10

Topics
Hash map, Simulation, Sorting
Solved
No attempts yet

Problem

There are many YouTubers in the world, and some of them are virtual YouTubers. A virtual YouTuber who streams live 55 times a week, with a total of at least 6060 hours of live streaming per week, is called a real virtual YouTuber. Hyeongsik likes virtual YouTubers and wants to find the real virtual YouTubers. Given NN lines, each with a YouTuber's name, a broadcast day, a start time, and an end time, print the names of the real virtual YouTubers in lexicographic order.

Day 11 is a Sunday. A week runs from Sunday to Saturday.

Input

The first line contains the number of broadcasts NN and the last day MM that Hyeongsik watched, separated by a space. (1≤N≤36 400;(1 \leq N \leq 36\,400; 7≤M≤364;7 \leq M \leq 364; MM is a multiple of 7)7)

The next NN lines each contain name day hh:mm hh:mm, separated by spaces: the YouTuber's name, the broadcast day, the start time, and the end time. (1≤day≤M)(1 \leq \text{day} \leq M) Times use the 24-hour clock. (0≤hh≤23;(0 \leq \text{hh} \leq 23; 0≤mm≤59)0 \leq \text{mm} \leq 59)

A name has at most 2020 characters, contains no spaces, and consists only of lowercase English letters. Names are distinct, so each name identifies one YouTuber. There are at most 100100 YouTubers.

A broadcast lasts at most 2323 hours and 5959 minutes. No broadcast starts on one day and continues past midnight into the next day, so the start and end dates are always the same. A YouTuber broadcasts at most once per day.

Output

Print the names of the real virtual YouTubers in lexicographic order, one per line. If there are none, print -1.

Hints

A broadcast that starts at 00:01 and ends at 01:20 lasts 1 hour and 19 minutes.

The start time is always earlier than the end time.

The input order may not be sorted by broadcast day.

Examples2

  1. Example 1

    Input
    24 7
    ai 1 20:00 21:30
    polka 1 16:00 16:30
    ange 1 22:00 23:30
    tsuna 1 00:00 05:00
    lita 1 05:00 06:30
    tsuna 2 03:00 20:00
    polka 2 00:00 20:01
    ange 2 01:00 23:30
    lita 3 01:00 23:30
    tsuna 3 10:00 23:00
    ai 3 10:00 23:00
    ange 4 06:00 20:00
    polka 4 10:00 23:00
    tsuna 5 07:00 20:00
    ange 5 11:00 23:00
    polka 5 07:00 13:00
    lita 5 03:00 23:00
    ange 6 00:00 11:01
    ai 6 00:00 20:00
    tsuna 6 14:00 23:00
    lita 6 00:00 17:00
    polka 6 13:00 20:00
    tsuna 7 16:00 22:00
    polka 7 06:00 09:28
    
    Expected output
    ange
    tsuna
    
  2. Example 2

    Input
    22 7
    ai 1 20:00 21:30
    polka 1 16:00 16:30
    lita 1 05:00 06:30
    tsuna 2 03:00 20:00
    polka 2 00:00 20:01
    ange 2 01:00 23:30
    lita 3 01:00 23:30
    tsuna 3 10:00 23:00
    ai 3 10:00 23:00
    ange 4 06:00 20:00
    polka 4 10:00 23:00
    tsuna 5 07:00 20:00
    ange 5 11:00 23:00
    polka 5 07:00 13:00
    lita 5 03:00 23:00
    ange 6 00:00 11:01
    ai 6 00:00 20:00
    tsuna 6 14:00 23:00
    lita 6 00:00 17:00
    polka 6 13:00 20:00
    tsuna 7 16:00 22:00
    polka 7 06:00 09:28
    
    Expected output
    -1