농장 제어 서비스 배포 점검

문제

여러 재배 구역의 장비를 관리하는 농장에서 DevOps 담당자가 제어 서비스의 배포 전 점검을 수행한다. 배포 후보 서비스에는 1번부터 S번까지 번호가 붙어 있다. 모든 후보는 현재 운영 서버에 설치된 공용 모듈을 사용한다. 담당자는 설치된 모듈 목록과 서비스별 의존성 조건을 받아 현재 서버에서 실행 가능한 후보를 골라야 한다. 각 모듈은 정수 코드로 구별하며, 서버에는 같은 코드의 모듈이 최대 하나 설치되어 있다. 모듈의 버전은 a.b.c 형식이다. a, b, c는 각각 0 이상 99 이하의 정수이며, 각 부분에는 값이 0인 경우를 제외하고 앞에 0을 붙이지 않는다. 두 버전은 a를 먼저 비교하고, a가 같으면 b를 비교하며, b도 같으면 c를 비교한다. 세 값이 모두 같을 때만 같은 버전이다. 따라서 버전 문자열 자체의 사전순이나 소수로 해석한 값으로 비교하지 않는다. 의존성 조건 하나는 서비스 번호, 모듈 코드, 허용하는 최소 버전과 최대 버전으로 이루어진다. 해당 모듈이 설치되어 있고 그 버전이 최소 버전 이상이면서 최대 버전 이하일 때만 조건을 만족한다. 양쪽 경계 버전은 모두 허용된다. 조건에 나온 모듈이 설치되어 있지 않으면 그 조건은 만족하지 않는다. 각 조건의 최소 버전은 최대 버전보다 크지 않다. 서비스는 자신에게 주어진 의존성 조건을 모두 만족할 때 배포 가능하다. 한 서비스에 같은 모듈의 조건이 여러 번 나올 수도 있으며, 이때도 모든 조건을 각각 만족해야 한다. 조건이 하나도 없는 서비스는 배포 가능하다. 이번 작업은 현재 상태를 검사하는 작업이므로 모듈을 설치하거나 버전을 변경하지 않는다. 또한 어떤 후보의 배포 가능 여부가 다른 후보의 판정에 영향을 주지 않는다. 배포 가능한 서비스의 개수와 번호 목록을 구한다.

입력

첫째 줄에 정수 N, S, R이 공백으로 주어진다. N은 설치된 모듈 수, S는 후보 서비스 수, R은 의존성 조건 수다.
다음 N개 줄에 모듈 코드 C와 설치 버전 V가 공백으로 주어진다. 이 목록의 모듈 코드는 서로 다르며 순서는 임의다.
다음 R개 줄에 서비스 번호 T, 모듈 코드 C, 최소 버전 L, 최대 버전 U가 공백으로 주어진다.
0 ≤ N ≤ 8,000
1 ≤ S ≤ 8,000
0 ≤ R ≤ 8,000
1 ≤ C ≤ 99,999
1 ≤ T ≤ S
모든 버전은 a.b.c 형식이며 a, b, c는 0 이상 99 이하의 정수다. 각 부분에는 불필요한 앞자리 0이 없다.
각 조건에서 L ≤ U이며 버전 비교는 본문의 규칙을 따른다. 서비스 번호와 모듈 코드는 정수다.

출력

첫째 줄에 배포 가능한 서비스의 개수 K를 출력한다. K가 양수이면 둘째 줄에 배포 가능한 서비스 번호를 오름차순으로 공백으로 구분하여 출력한다. K가 0이면 둘째 줄에 -1을 출력한다.

3 4 5
71 1.10.0
8 2.0.5
24 0.9.9
1 71 1.2.0 1.10.0
1 8 2.0.0 2.0.5
2 24 0.9.0 0.9.8
3 99 0.0.0 99.99.99
3 71 1.0.0 2.0.0

2
1 4

0 3 3
1 5 0.0.0 0.0.0
2 8 1.0.0 2.0.0
3 5 0.0.0 99.99.99

0
-1

1 3 3
15 3.2.7
1 15 3.2.7 3.2.7
2 15 3.0.0 3.2.7
2 15 3.2.8 4.0.0

2
1 3

출처: Devin.KR 자체 제작