정산 서버 버전 범위 점검

문제

한 주차장 운영 회사는 차량 번호판을 읽는 장비와 요금 정산 서버를 여러 대 운영하며, 각 서버에 설치된 소프트웨어의 버전을 점검한다. 버전은 점으로 구분된 음이 아닌 정수 여러 개로 이루어진 문자열이다. 예를 들어 1.2.10은 세 정수 1, 2, 10으로 이루어진다. 각 정수는 앞에 0이 붙어 있을 수 있으며, 이때는 정수 값으로 읽는다. 즉 01.002는 1.2와 같다. 두 버전을 비교할 때는 앞 정수부터 차례로 값을 비교하고, 한쪽이 먼저 끝나면 끝난 쪽의 나머지 정수를 모두 0으로 본다. 따라서 1.2와 1.2.0.0은 같은 버전이고, 1.2는 1.2.1보다 작다. 현재 설치된 버전이 N개 주어진다. 같은 버전이 여러 번 나올 수 있으며 각각 따로 센다. 질문은 Q개이며 두 종류이다. 종류 1은 두 버전 L, R이 주어지고, L 이상 R 이하인 설치 버전의 개수를 묻는다. L이 R보다 크면 답은 0이다. 종류 2는 버전 X가 주어지고, X 이상이면서 X와 첫 번째 정수(주 버전)가 같은 설치 버전의 개수를 묻는다. 각 질문의 답을 입력 순서대로 한 줄에 하나씩 출력하는 프로그램을 작성하라.

입력

첫 줄에 N과 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 200000) 다음 N개의 줄에 설치된 버전이 하나씩 주어진다. 다음 Q개의 줄에 질문이 하나씩 주어진다. 질문은 "1 L R" 또는 "2 X" 형식이다. 모든 버전은 정수 1~10개를 점으로 구분한 문자열이며, 각 정수는 십진수 숫자로만 이루어지고 값은 0 이상 10^9 이하이다. 정수의 앞에 0이 붙을 수 있다. 입력 전체의 길이는 400KB 이하이다.

출력

질문마다 답을 한 줄에 하나씩 출력한다.

5 4
1.2
1.2.0
1.10
2.0.1
0.9.9
1 1.2 1.10
2 1.5
1 1.2.0.0 1.2
1 2.0 1.0

3
1
2
0

3 2
0
0.0.1
0.00
2 0.0
2 1

3
0

출처: Devin.KR 자체 제작