公交车站(Bus Station)

题目描述

有一个公交车站，陆续有若干乘客前来排队，也陆续会有一些班车将乘客运走。

共有 n 班公交车停靠该车站，对班车 i，有一个时间参数 a_i，表示它到达车站的时间，以及另外一个装载参数 d_i，表示这一班车能装载的乘客数量：

• 若排队人多，则优先载运到达时间靠前的乘客；
• 若排队人少，座位还有剩余，班车不会等待。

共有 m 位乘客来该站点候车，每名乘客有两个时间参数。

• 乘客 j 的第一个参数表示他的到达时间 s_j；
• 第二个参数表示他的离开时间 t_j。太过漫长的等待会令人失去耐心。若他在时间 t_j 前不能上车，乘客 j 就会离开车站，选择其他交通方式。
• 若存在两位乘客的到达时间完全一致，则按输入时他们的序号顺序依次排队候车。例如：2 号乘客和 5 号乘客的到达时间相同，我们认为2号乘客排在 5 号乘客前面。

班车到站时间 a_i、乘客的到达与离开时间 s_i, t_i 均以 24 小时制时间给出，以 HH:MM 形式表示，例如8点30分表示为 08:30，小时与分钟均为两位数，不足两位时，首位以 0 补全。

给定所有乘客以及所有班车的信息，请对于每一个乘客，输出他在车站等待上车的时长（单位为分钟），若该乘客放弃等待离开车站，则输出 Leave。

输入格式

第一行，两个正整数 n 和 m； 接下来 n 行，每行两个参数 a_i, d_i，表示第 i 号班车的到达时间与最大载客数量。 接下来 m 行，每行两个参数 s_i, t_i，表示第 i 号乘客的到达时间与离开时间。

输出格式

共 m 行：表示 m 个乘客的等待时间长度。

样例输入 #1

3 6
09:10 3
08:30 2
10:20 4
09:05 09:15
09:01 09:22
08:31 09:20
09:05 10:00
10:10 10:15
08:30 08:33

样例输出 #1

5
9
39
Leave
Leave
0

说明： 1，2，3号乘客选乘09:10这班车，等待时间分别为5分钟、9分钟、39分钟。 4号乘客和1号乘客到达时间相同，排在1号乘客后面，因载客量未能乘09:10这班车，直到放弃时间没有公交车前来，则放弃乘坐。 5号乘客直到放弃时间没有公交车前来，则放弃乘坐。 6号乘客到站直接乘坐08:30这班车，等待时长为0分钟。

数据范围

• 对于 30% 的数据，1 ≤ n ≤ 5, 1 ≤ m ≤ 10
• 对于 50% 的数据，1 ≤ n ≤ 100, 1 ≤ m ≤ 1000
• 对于 100% 的数据，1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000

数据保证所有 24 小时制的时间数字是合理的，并且所有的时间区间不会出现跨过某天零点的情况。

知识点与难度

本题涉及的知识点从属于 GESP 4级，难度等级：⭐⭐⭐。

测试点分布