在moxin把电脑翻新之后,网吧生意日渐红火。他很是开心,听起了歌。常来他家网吧的几个人看到此景,给moxin抛出了一个问题:
当你在听歌的时候,如果你把进度条拉到歌的某个时间点,听歌软件会立刻显示当前时间点的歌词。能有这么大场面的老板一定不简单,我们这里给你一首歌的歌词以及询问的时间点,只要你能在限定的时间内答出每一个时间点对应的歌词,我们就帮你把剩下的坏电脑也换了!
犹豫就会败北,moxin听到这个请求,立马爽快的答应了。可是他尝试以后发现自己并不能很快的解决这个问题,所以还请你来帮他解决一下。
请注意,如果询问的时间点比第一句歌词所开始的时间还早,请输出第一句歌词。
输入的第一行由两个正整数 n 和 q 组成,分别表示歌词条数与询问数。
接下来的 n 行表示歌词,输入按此格式:[小时:分钟:秒钟.毫秒] 歌词内容。
其中,歌词的时间点满足:小时∈[0, 99],分钟∈[0, 59],秒钟∈[0, 59],毫秒∈[0, 999]。长度不够会用0补齐。
接下来的 q 行表示询问,每行含四个整数,分别表示询问的小时、分钟、秒钟及毫秒。范围与歌词时间点相同。
另外:
1 ≤ n ≤ 104,1 ≤ q ≤ 105。
歌词内容字符串的任一字符保证为以下字符之一 :0-9,A-Z,a-z,逗号,小数点,左圆括号,右圆括号,单引号,双引号,减号;
歌词内容字符串不以空格开头,不以空格结尾,长度 ∈ [1, 30]。
n 行歌词给出的顺序是按照时间顺序的,且不存在相邻两句歌词,它们的时间相同。
输出 q 行:对于每一个询问,输出该时间对应的歌词内容。
5 4 [00:00:16.393] Say you, say me [00:00:21.921] Say it for always [00:00:26.174] That's the way it should be [00:00:31.472] Say you, say me [00:00:37.001] Say it together, naturally 0 0 31 472 0 0 16 390 0 0 25 0 0 0 37 2
Say you, say me Say you, say me Say it for always Say it together, naturally