세탁소 제어 서버 업데이트

문제

한 세탁소의 DevOps 담당자는 세탁 장비를 관리하는 제어 프로그램의 업데이트 후보를 검토하고 있다. 제어 서버에는 현재 사용 중인 제어 프로그램과 실행 환경이 각각 하나씩 설치되어 있다. 이번 작업에서는 실행 환경을 바꾸지 않고 제어 프로그램만 새 버전으로 교체하려 한다. 후보마다 요구하는 실행 환경의 버전 범위가 다르므로, 프로그램 버전이 높다는 이유만으로 설치할 수는 없다. 이 문제의 모든 버전은 점으로 구분한 세 정수 a.b.c로 표시한다. 세 정수는 각각 0 이상 999 이하이며, 0 자체를 제외하면 앞에 불필요한 0을 붙이지 않는다. 버전을 비교할 때는 먼저 a를 비교하고, 같으면 b를 비교하며, 이 값도 같으면 c를 비교한다. 처음으로 다른 정수가 큰 쪽이 더 높은 버전이다. 세 정수가 모두 같으면 같은 버전이다. 예를 들어 4.12.0은 4.9.999보다 높다. 버전을 소수나 문자열의 사전 순서로 비교하지 않는다. 각 후보에는 제어 프로그램 버전 V, 설치에 필요한 실행 환경의 최소 버전 P, 허용하는 최대 버전 Q가 주어진다. 현재 실행 환경 버전이 P 이상 Q 이하이고, V가 현재 제어 프로그램 버전보다 엄격히 높을 때만 설치 가능한 후보가 된다. 최소 버전과 최대 버전은 모두 허용 범위에 포함된다. 현재 프로그램과 같은 버전은 재설치 대상으로 선택하지 않는다. 설치 가능한 후보 중 제어 프로그램 버전이 가장 높은 후보 하나를 선택한다. 같은 프로그램 버전을 가진 후보가 여러 개 설치 가능하면 입력에서 먼저 나온 후보를 선택한다. 각 후보의 번호는 입력된 순서대로 1부터 N까지다. 후보끼리 연결하여 여러 번 업데이트하는 과정은 고려하지 않으며, 모든 후보는 처음 주어진 서버 상태를 기준으로 판단한다. 설치 가능한 후보가 하나도 없으면 업데이트를 진행하지 않는다. 담당자가 선택해야 할 후보 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 현재 제어 프로그램 버전 C와 현재 실행 환경 버전 R이 공백으로 구분되어 주어진다.
둘째 줄에 후보 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 10,000이다.
다음 N개 줄에는 각 후보의 버전 V, 최소 실행 환경 버전 P, 최대 실행 환경 버전 Q가 공백으로 구분되어 주어진다. 항상 P ≤ Q다.
모든 버전은 a.b.c 형식이며 a, b, c는 0 이상 999 이하인 정수다. 각 구성 요소에는 0 자체를 제외한 선행 0이 없다. 같은 후보 정보가 여러 번 주어질 수 있다.

출력

선택한 후보의 번호를 정수 하나로 출력한다. 설치 가능한 후보가 없으면 0을 출력한다.

2.9.0 3.5.0
5
2.10.0 3.0.0 3.9.0
3.0.0 3.5.1 4.0.0
2.10.0 3.5.0 3.5.0
2.9.0 0.0.0 9.0.0
2.8.999 0.0.0 9.0.0

1

1.0.0 2.0.0
3
1.0.0 2.0.0 2.0.0
1.0.1 2.0.1 3.0.0
9.0.0 0.0.0 1.999.999

0

4.9.999 7.2.0
3
4.10.0 7.0.0 7.2.0
4.12.0 7.2.0 8.0.0
4.11.999 0.0.0 9.0.0

2

출처: Devin.KR 자체 제작