메신저 확장 기능 배포 점검

문제

사내 메신저를 운영하는 DevOps 담당자는 새 확장 기능을 배포하기 전에 서버의 모듈 버전을 점검한다. 각 확장 기능은 실행에 필요한 모듈 번호와 그 모듈의 최소 버전을 점검 목록에 남긴다. 여러 확장 기능이 같은 모듈을 사용할 수 있으므로, 점검 목록에는 같은 모듈에 대한 요구가 여러 번 나타날 수 있다. 담당자는 이 목록 전체를 만족하지 못하는 모듈 번호를 알아내야 한다. 버전은 세 정수 A, B, C로 나타낸다. 두 버전을 비교할 때는 먼저 A를 비교하고, A가 같으면 B를 비교하며, A와 B가 모두 같으면 C를 비교한다. 처음으로 다른 위치에서 더 큰 정수를 가진 버전이 더 높은 버전이다. 세 정수가 모두 같으면 같은 버전이다. 각 정수는 독립적인 수이므로 자릿수를 이어 붙이거나 세 정수의 합으로 비교하지 않는다. 하나의 요구는 해당 모듈이 서버에 설치되어 있고 설치 버전이 요구한 최소 버전 이상일 때 만족한다. 설치 버전이 요구 버전과 정확히 같아도 만족한다. 설치되지 않은 모듈에 대한 요구는 최소 버전이 무엇이든 만족하지 못한다. 서버에는 같은 번호의 모듈이 두 번 설치되어 있지 않다. 점검 목록에서 한 번이라도 요구를 만족하지 못한 모듈은 점검 대상이다. 같은 모듈이 여러 요구를 만족하지 못하더라도 결과에는 그 번호를 한 번만 적는다. 반대로 여러 요구 중 일부만 만족해도 나머지 요구를 만족하지 못했다면 점검 대상이다. 설치되어 있지만 점검 목록에 등장하지 않는 모듈은 결과에 넣지 않는다. 점검 도중 설치 버전은 바뀌지 않으며, 실제 설치나 업데이트 작업은 수행하지 않는다. 점검 대상 모듈의 개수와 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 설치된 모듈 수 N과 요구 수 M이 주어진다. 다음 N개 줄은 설치 정보이며, 이어지는 M개 줄은 요구 정보다. 각 정보는 모듈 번호 X와 버전을 나타내는 A B C의 네 정수로 주어진다. 모든 값은 정수이며 0 ≤ N, M ≤ 20,000, 1 ≤ N + M ≤ 20,000, 0 ≤ X ≤ 999, 0 ≤ A, B, C ≤ 99다. 설치 정보의 X는 서로 다르므로 N ≤ 1,000이다. 요구 정보의 X는 중복될 수 있다.

출력

첫째 줄에 점검 대상 모듈 수 K를 출력한다. K가 양수이면 둘째 줄에 해당 모듈 번호를 오름차순으로 공백으로 구분하여 출력한다. K가 0이면 첫째 줄의 0만 출력한다.

3 5
14 2 3 0
8 1 10 0
25 0 0 0
14 2 2 99
14 2 3 1
8 1 9 99
30 0 0 0
14 3 0 0

2
14 30

2 2
4 1 0 0
9 0 12 3
4 1 0 0
9 0 11 99

0

0 2
7 0 0 0
7 0 0 1

1
7

출처: Devin.KR 자체 제작