공통 모듈 배포 점검

문제

한 온라인 쇼핑몰은 상품 조회, 주문 처리, 배송 안내 등 여러 서비스를 운영한다. 이 서비스들은 같은 공통 모듈을 사용한다. DevOps 담당자는 공통 모듈을 새 버전으로 배포하기 전에 각 서비스가 그 버전을 지원하는지 점검하려 한다. 입력에는 배포할 후보 버전 V와 각 서비스의 의존성 허용 범위가 주어진다. 버전은 점으로 구분한 세 정수 a.b.c로 표시한다. 각 정수는 0 이상 99 이하이며, 값이 0인 경우를 제외하고 앞에 불필요한 0을 붙이지 않는다. 두 버전을 비교할 때는 첫 번째 정수부터 비교한다. 첫 번째 정수가 같으면 두 번째 정수를 비교하고, 두 번째 정수도 같으면 세 번째 정수를 비교한다. 처음으로 서로 다른 위치에서 정수가 큰 쪽이 더 높은 버전이다. 세 정수가 모두 같으면 같은 버전이다. 각 자리를 문자열의 사전순으로 비교해서는 안 된다. 각 서비스에는 최소 허용 버전 L과 허용하지 않는 버전의 시작 U가 기록되어 있다. 서비스는 L 이상 U 미만인 버전만 지원한다. 따라서 후보 버전이 L과 같으면 지원하지만 U와 같으면 지원하지 않는다. 입력의 모든 서비스에서 L은 U보다 낮다. 후보 버전이 이 범위를 벗어나면 해당 서비스는 배포 전에 확인이 필요한 서비스가 된다. 서비스에는 1부터 N까지의 서로 다른 식별 번호가 하나씩 부여되어 있다. 의존성 기록은 식별 번호순으로 들어온다는 보장이 없으며, 여러 서비스의 허용 범위가 같을 수 있다. 서비스끼리 추가 의존성은 없으므로 각 범위를 독립적으로 판단한다. 확인이 필요한 서비스의 수와 식별 번호를 구한다. 식별 번호는 작은 순서대로 출력하고, 해당 서비스가 없으면 수를 나타내는 0만 출력한다.

입력

첫째 줄에 서비스 수를 나타내는 정수 N이 주어진다.
둘째 줄에 후보 버전 V가 주어진다.
다음 N개의 줄에 서비스 식별 번호 I, 최소 허용 버전 L, 허용하지 않는 버전의 시작 U가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 12,000이다. 식별 번호는 1부터 N까지 각각 정확히 한 번 등장한다.
모든 버전은 a.b.c 형식이며 a, b, c는 각각 0 이상 99 이하의 정수이다. 각 구성 정수에는 불필요한 앞자리 0이 없다.
모든 기록에서 버전 비교 기준으로 L < U이다.

출력

첫째 줄에 확인이 필요한 서비스의 수 K를 출력한다. K가 양수이면 둘째 줄에 해당 서비스의 식별 번호 K개를 오름차순으로 공백으로 구분하여 출력한다. K가 0이면 둘째 줄 없이 첫째 줄만 출력한다.

4
2.10.0
3 2.9.9 2.10.0
1 2.10.0 3.0.0
4 2.11.0 4.0.0
2 1.0.0 2.10.1

2
3 4

2
0.0.0
2 0.0.0 0.0.1
1 0.0.0 99.99.99

0

3
10.0.0
2 2.0.0 9.99.99
3 10.0.1 11.0.0
1 9.0.0 10.0.0

3
1 2 3

출처: Devin.KR 자체 제작