어느 건물의 출입문에는 사람이 지나갈 때마다 그 시각을 기록하는 장치가 달려 있다.

하루 동안 기록된 출입 시각 \(N\)개가 주어진다. 시각은 hh:mm 형식이며, 00:00부터 23:59까지의 값이다.

기록은 시간 순서대로 주어지지 않으며, 같은 시각이 여러 번 기록될 수도 있다.

경비원은 "시각 \(s\)부터 시각 \(e\)까지 몇 번 출입했는가?"라는 질문을 \(Q\)번 한다.

두 시각 \(s\)와 \(e\)도 같은 날의 시각이며, 구간은 양 끝 시각을 모두 포함한다.

• \(s\)가 \(e\)보다 이르거나 같으면, \(s\) 이상 \(e\) 이하인 기록의 개수를 센다.
• \(s\)가 \(e\)보다 늦으면, 구간이 자정을 넘어가는 것으로 본다. 즉, \(s\)부터 23:59까지의 기록과 00:00부터 \(e\)까지의 기록을 모두 센다.

각 질문에 대한 답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 기록의 개수 \(N\)과 질문의 개수 \(Q\)가 공백으로 구분되어 주어진다.

둘째 줄에 출입 시각 \(N\)개가 hh:mm 형식으로 공백으로 구분되어 주어진다.

셋째 줄부터 \(Q\)개의 줄에 걸쳐 질문이 한 줄에 하나씩 주어진다. 각 질문은 두 시각 \(s\)와 \(e\)가 hh:mm 형식으로 공백으로 구분되어 주어진다.

출력

\(Q\)개의 줄에 걸쳐, 각 질문에 대한 답을 질문이 주어진 순서대로 한 줄에 하나씩 출력한다.

제한 사항

• \(1 \le N \le 100,000\)
• \(1 \le Q \le 100,000\)
• 모든 시각은 00:00 이상 23:59 이하이며, 시와 분은 항상 두 자리로 주어진다.

예제 입력 1

7 4
09:00 13:30 08:15 23:50 00:10 13:30 18:05
08:00 13:30
22:00 02:00
13:30 13:30
14:00 18:00

예제 출력 1

4
2
2
0

예제 입력 2

3 3
00:00 23:59 12:00
00:00 23:59
23:59 00:00
12:01 11:59

예제 출력 2

3
2
2

노트

예제 1의 첫 번째 질문에서 08:00부터 13:30까지의 기록은 08:15, 09:00, 13:30, 13:30의 \(4\)개이다.

두 번째 질문은 자정을 넘어가므로 22:00부터 23:59까지의 23:50과 00:00부터 02:00까지의 00:10을 세어 \(2\)개이다.

세 번째 질문처럼 \(s\)와 \(e\)가 같으면 그 시각의 기록만 센다.

예제 2의 세 번째 질문은 12:01부터 다음 날 11:59까지이므로, 12:00의 기록은 포함되지 않는다.