小鱼干的计划

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小鱼干做事喜欢有计划有条理,作为一个零食控,她会在自己想吃零食的某一天买一种零食,并预估这种零食可以持续食用的天数,然后她会在将来连续的若干天里(包括当天)的指定时刻持续吃这一种零食,比如A零食第一天是10:23:33吃的,那么第二天也是10:23:33吃,第三天也是……。当然,对于一个资深的吃货,小鱼干吃东西的速度是惊人的,也就是说她一秒钟可以吃完一种零食。当然为了践行自己的吃货价值观,她吃零食是不带重样的,并且她不会安排自己在同一秒内食用多种零食。可是她不光能吃,还想减肥,所以为了幻想自己的减肥计划,她需要知道自己在某一天的某一时间段内食用零食的种数。但是鱼只有七秒钟的记忆,所以她根本不记得自己吃了啥……所以,这时候,她需要一个经纪人……



……喂,想啥呢,是需要一个经纪人来帮她记录并计算某一天的某一时间段内吃的零食的种数,作为老司机,怎能错过经纪人的职务,你们来帮她一下。

Input

 多组输入,对于每组数据第一行两个整数n,m(0 < n,m <= 10^5),分别代表零食的种类数量和查询的次数。

接下来的n行,每行一条指令,描述了一种零食的信息,格式如下所示:

year1-month1-day1 hh:mm:ss year2-month2-day2

其中,year1,month1,day1是三个"-"间隔的整数,表示年月日,开始食用的日期(1970<=y<2147483648,给定的日期保证合法);hh,mm,ss是三个":"间隔的整数,代表时分秒(24小时制,保证给定时间合法);year2,month2,day2同上,代表该零食可以持续食用到的日期(包含当日,保证不早于开始食用的日期)。

接下来的m行,每行给出一个日期和一个时间段,代表查询,格式如下:

year-month-day hh1:mm1:ss1 hh2:mm2:ss2

各字段的含义同上。其中,空格间隔的三部分,第一部分是日期,第二部分是查询的起始时间,第三部分是查询的终止时间。查询的区间包含端点且保证起始时间不晚于终止时间。

 

注意:给定的零食信息不保证时间有序,但保证给定的查询时间是有序的。

Output

 每组数据输出m行查询结果。

对于每次查询操作输出一个整数,表示这一天的这一时间段内吃的零食的种数,每个结果占一行。

Sample Input

2 2
2016-8-23 10:23:33 2016-8-25
2016-8-25 11:23:33 2016-8-27
2016-8-25 10:23:33 11:23:33
2016-8-28 00:00:00 23:59:59
5 9
2016-8-23 10:23:33 2016-8-25
2016-8-25 11:23:33 2016-8-27
2016-8-26 11:23:32 2016-10-10
2016-1-1 23:23:23 2017-1-1
2016-8-30 00:00:00 2016-8-30
2016-8-25 10:23:33 11:23:33
2016-8-28 00:00:00 23:59:59
2016-8-30 00:00:00 00:00:00
2016-8-30 00:00:00 11:23:31
2016-8-30 00:00:00 11:23:32
2016-8-30 00:00:00 11:23:33
2016-8-30 00:00:00 23:59:59
2016-8-30 00:00:01 11:23:31
2016-8-30 00:00:01 11:23:32

Sample Output

2
0
2
2
1
1
2
2
3
0
1

Hint

Source

2016暑假集训结训赛 by Shannon