학원 실습 도구 버전 범위 점검

문제

학원 전산실에는 수강생용 컴퓨터가 N대 있고, 각 컴퓨터에는 수업용 실습 도구가 하나씩 설치되어 있다. 도구의 버전은 점으로 구분된 1개 이상 4개 이하의 음이 아닌 정수 조각으로 적는다. 예를 들어 1.2, 3.0.14, 2.10.0.7과 같다. 각 조각은 0 이상 999999 이하의 정수이며, 값이 0인 조각이 아니면 앞에 0이 붙지 않는다. 두 버전은 조각을 앞에서부터 차례로 숫자 크기로 비교해 크기를 정한다. 조각 수가 모자란 쪽은 뒤쪽 빈 조각을 0으로 채워서 비교한다. 따라서 1.2와 1.2.0은 같은 버전이고, 1.10은 1.9보다 크며, 1.2.0.1은 1.2보다 크고 1.3보다 작다. DevOps 담당자는 업데이트 점검을 위해 Q개의 질의를 던진다. 각 질의는 두 버전 lo와 hi로 이루어진다. 설치 버전이 lo 이상 hi 이하인 컴퓨터가 몇 대인지, 그리고 그 컴퓨터들이 가진 서로 다른 버전이 몇 종류인지를 구한다. 표기가 달라도 크기가 같은 버전(예: 1.2와 1.2.0)은 한 종류로 센다. lo가 hi보다 크면 조건을 만족하는 컴퓨터가 없으므로 두 값 모두 0이다.

입력

첫 줄에 컴퓨터 수 N과 질의 수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 20000, 1 ≤ Q ≤ 10000) 이어서 N개의 줄에 각 컴퓨터에 설치된 버전이 한 줄에 하나씩 주어진다. 이어서 Q개의 줄에 질의의 lo와 hi가 공백으로 구분되어 주어진다. 모든 버전은 위에서 설명한 형식을 지킨다.

출력

각 질의마다 한 줄에 조건을 만족하는 컴퓨터 수와 서로 다른 버전 종류 수를 공백으로 구분해 출력한다.

5 3
1.2
1.2.0
1.10
2
1.2.0.1
1.2 1.2.0
1.2.0.1 1.10
1.3 1.9

2 1
2 2
0 0

3 2
0
0.0.0
0.0.1
0 0.0.0.0
0.0.1 0

2 1
0 0

출처: Devin.KR 자체 제작