최후의 카운트다운

닥터 둠은 나사(NASA)의 미션 컨트롤을 본떠 LAI-BACH(라트베리아 항공우주 연구소, 볼로그라드 능동 제어 본부)를 만들면서, 원본을 조금 지나치게 그대로 베낀 듯하다.

나사, 그리고 그를 본뜬 LAI-BACH는 발사 카운트다운을 독특한 방식으로 처리한다. 시계상으로는 예를 들어 발사까지 30분이 남았다고 표시되더라도, 시계가 일정 시간 동안 멈추는 미리 정해진 정지(hold) 구간이 존재한다. 예컨대 카운트다운이 8분 지점에 도달하면 15분짜리 정지가 있을 수 있다. 그 결과 카운트다운의 시작부터 끝까지 실제로 흐르는 시간은 시계의 숫자가 의미하는 것보다 더 길어진다.

LAI-BACH는 컴퓨터 시스템에서 카운트다운의 정지를 관리하기 위해 간단한 "명령 파일" 형식을 사용한다. 모든 명령은 1440 이하의 양의 정수(하루를 넘는 카운트다운은 닥터 둠을 화나게 한다)로 시작하고, 그 뒤에 지시어가 온다. 명령의 형태는 다음과 같다.

각 condition은 소문자로 이루어진 최대 20자의 짧은 문자열이다. 그 실제 값은 명령 파일에 주어지지 않는데, 발사 당시의 실제 상황(연료 탱크를 가득 채웠는지, 판타스틱 4가 지금 닥터 둠과 싸우고 있는지 등)에 따라 결정되기 때문이다. 그렇더라도 각 condition은 항상 참 또는 거짓 중 하나이며, 하나의 카운트다운이 진행되는 동안에는 값이 바뀌지 않는다. 정지 시간 n은 60분 이하의 양의 정수인데, 긴 지연 역시 빅터를 짜증나게 하기 때문이다.

정지는 시계가 실제로 그 시각 t에 도달할 때에만 카운트다운에 영향을 준다. 시계는 시작 시각에서 0까지 줄어들므로, 시각 t가 시작 시각 이상인 정지는 결코 일어나지 않는다.

명령 파일이 주어졌을 때, 카운트다운이 걸릴 수 있는 가장 짧은 시간과 가장 긴 시간을 모두 구하여라. 명령은 임의의 순서로 나타날 수 있고, START 지시어는 항상 정확히 하나 존재하며, 각 줄에는 위 형식에 명시된 만큼의 공백이 정확히 들어 있고, 어떤 두 명령도 같은 분 t를 가리키지 않는다.

입력의 첫 줄에는 데이터 집합의 개수를 나타내는 정수 N (1 ≤ N ≤ 100)이 주어진다. 각 데이터 집합은 다음으로 구성된다.

• "명령 파일"의 줄 수를 나타내는 정수 L (1 ≤ L ≤ 100)이 있는 한 줄; 그리고
• 위에서 설명한 형식으로 된, 명령 파일을 이루는 L개의 줄.

각 데이터 집합에 대해 min TO max 형태로 한 줄에 출력한다. 여기서 min은 카운트다운이 지속될 수 있는 가장 짧은 시간(분), max는 가장 긴 시간(분)이다.