관측 장비의 공통 배포 버전

문제

날씨 관측소의 DevOps 담당자는 여러 관측 프로그램이 함께 사용하는 통신 모듈의 배포 버전을 정하려 한다. 프로그램마다 호환되는 모듈 버전의 범위가 다르지만, 이번 배포에서는 모든 프로그램에 같은 모듈 버전을 설치해야 한다. 배포 저장소에는 실제로 설치할 수 있는 버전들이 등록되어 있다. 호환 범위 안에 있는 버전이라도 저장소에 없다면 선택할 수 없다. 버전은 a.b.c 형태이며 a, b, c는 각각 0 이상 999 이하의 정수이다. 각 부분은 값이 0일 때의 한 자리 표기를 제외하면 앞에 0을 붙이지 않는다. 두 버전은 먼저 a를 비교하고, a가 같으면 b를 비교하고, b도 같으면 c를 비교한다. 처음으로 다른 부분의 값이 큰 버전이 더 높은 버전이다. 세 부분이 모두 같으면 같은 버전이다. 따라서 각 부분의 자릿수나 버전 문자열 전체의 사전순으로 높낮이를 정해서는 안 된다. 각 관측 프로그램은 허용하는 가장 낮은 버전 L과 가장 높은 버전 U를 하나씩 제출한다. 해당 프로그램은 L 이상 U 이하인 버전을 사용할 수 있으며, 양 끝 버전도 허용한다. 프로그램별 범위는 각각 유효하지만, 모든 프로그램의 범위를 동시에 만족하는 버전이 존재한다는 보장은 없다. 모든 프로그램의 요구는 같은 중요도를 가지므로 일부 프로그램의 요구를 무시할 수 없다. 담당자는 불필요한 변경을 줄이기 위해 모든 요구를 만족하는 저장소 버전 중 가장 낮은 버전을 선택한다. 저장소의 입력 순서에는 의미가 없고 같은 버전이 여러 번 등록될 수도 있다. 중복 등록은 선택 결과에 영향을 주지 않는다. 선택할 수 있는 버전이 하나도 없으면 배포를 진행할 수 없다는 표시를 출력한다. 프로그램 사이의 추가 의존 관계나 현재 설치된 버전은 없으며, 입력에 주어진 호환 범위와 저장소 목록만으로 결과를 결정한다.

입력

첫째 줄에 저장소 항목 수 M과 관측 프로그램 수 N이 공백으로 주어진다. M과 N은 정수이며 1 ≤ M, N ≤ 200,000이다.
다음 M개 줄에 저장소 버전이 하나씩 주어진다.
다음 N개 줄에 각 프로그램의 허용 하한 L과 허용 상한 U가 공백으로 주어진다. 버전 비교 규칙에 따라 L ≤ U이다.
모든 버전은 지문에 정의된 형식을 따른다. 입력 전체의 크기는 줄바꿈과 공백을 포함하여 400,000바이트 이하이다.

출력

모든 프로그램이 허용하는 저장소 버전 중 가장 낮은 버전을 한 줄에 출력한다. 각 부분은 앞에 불필요한 0이 없는 a.b.c 형태로 출력한다. 선택할 수 있는 버전이 없으면 NONE을 출력한다.

5 2
2.10.0
2.9.8
3.0.0
2.10.3
2.10.0
2.9.9 2.10.5
2.10.0 3.0.0

2.10.0

3 2
1.0.0
1.5.0
2.0.0
1.0.0 1.2.0
1.3.0 2.0.0

NONE

2 1
0.0.0
4.0.0
1.0.0 3.9.999

NONE

출처: Devin.KR 자체 제작