배달 서비스 버전 호환 점검

문제

배달 앱을 운영하는 DevOps 엔지니어가 서버에 설치된 서비스 모듈 N개의 버전 목록을 가지고 있다. 새 배포를 앞두고, 각 모듈이 요구하는 의존성 조건 Q개에 대해 조건을 만족하는 설치 버전이 몇 개인지 세어야 한다. 버전은 점으로 구분된 1개 이상 3개 이하의 비음수 정수로 이루어지며 각 정수는 0 이상 999999 이하이고 0이 아니면 앞에 0이 붙지 않는다. 버전은 숫자로서 왼쪽 성분부터 비교하며, 빠진 성분은 0으로 본다. 따라서 2와 2.0과 2.0.0은 같은 버전이고, 1.10은 1.2보다 크다. 조건은 연산자와 버전을 공백 없이 붙인 문자열이다. >=v, >v, <=v, <v는 각각 v 이상, 초과, 이하, 미만인 버전을 뜻하고 =v는 v와 같은 버전을 뜻한다. ^x.y.z는 x.y.z 이상이고 (x+1).0.0 미만인 버전을, ~x.y.z는 x.y.z 이상이고 x.(y+1).0 미만인 버전을 뜻한다. 이때 ^와 ~에서 빠진 성분은 0으로 채워 해석하며, y+1이 1000000이 되면 그 경계는 (x+1).0.0과 같다고 본다. 설치된 버전 중 같은 버전이 여러 번 나올 수 있고 중복은 각각 센다. 각 조건에 대해 만족하는 설치 버전의 개수를 구하라. 조건을 만족하는 버전이 없으면 0을 출력한다.

입력

첫째 줄에 N과 Q가 공백으로 구분되어 주어진다. 다음 N개의 줄에 설치된 버전이 한 줄에 하나씩 주어진다. 다음 Q개의 줄에 조건이 한 줄에 하나씩 주어진다. 1 ≤ N, Q ≤ 200,000 이다. 조건의 연산자는 >=, >, <=, <, =, ^, ~ 중 하나이다.

출력

각 조건마다 만족하는 설치 버전의 개수를 한 줄에 하나씩 순서대로 출력한다.

5 5
1.2.3
1.10
2
1.2.3
0.9.9
>=1.2.3
^1.2
~1.2.3
<1
=2

4
3
2
1
1

2 3
999999.999999.999999
0
^999999
~0.999999
>0

1
0
1

출처: Devin.KR 자체 제작