알파 센타우리를 도는 운송 로봇

27세기 초, 알파 센타우리는 은하 이 구역의 중심 물류 거점이 되었다. 네 번째 행성 근처의 우주 정거장에서는 거의 모든 우주 문명의 물건이 거래되어 주요 항성계로 운송된다. 정거장은 큰 고리(원) 모양이며, 바깥 테두리에는 시계 방향으로 1부터 n까지 번호가 매겨진 접안 포트가 있다.

무역선이 포트에 접안하면, 보통 자신의 화물을 다른 포트에 접안한 다른 배로 옮기도록 요청한다. 이 일은 고리 안쪽에서 움직이는 운송 로봇(transrob)이 맡는다. 운송 로봇은 정거장을 시계 방향으로만 이동하며, 포트에서 화물을 싣고 내린다.

모든 배의 화물은 운송 컨테이너 하나에 들어가며, 각 운송 로봇은 한 번에 컨테이너 하나만 실을 수 있다. 운송 로봇끼리의 차이는 실을 수 있는 최대 무게뿐이다.

정거장을 운영하는 컨소시엄은 시스템을 개선하기 전에 현재 시스템의 성능 통계를 얻고자 한다. 구체적으로 다음 두 가지가 필요하다.

• 요청 처리의 평균 시간. 즉, 배가 운송을 요청한 순간부터 화물이 목적지에 실제로 배달될 때까지 걸린 시간의 평균.
• 운송 로봇의 가동률. 즉, 특정 시간 구간 동안 요청을 처리하고 있는 운송 로봇의 평균 비율.

이를 위해 시뮬레이션 프로그램을 작성해야 한다. 제어 프로그램의 동작은 다음과 같다.

• 운송 로봇은 1부터 m까지 번호가 매겨져 있다.
• 한 포트에서 다음 포트로 이동하는 데 1분이 걸리고, 컨테이너를 싣거나 내리는 데 5분이 걸린다.
• 운송 로봇은 각각 다른 궤도를 달리므로 서로 방해하지 않는다.
• 운송 로봇은 유휴(idle) 상태이거나 요청을 처리 중이다. 요청 처리는 요청의 출발지로 이동해 화물을 싣고, 목적지로 이동해 화물을 내린 뒤 다시 유휴 상태가 되는 것을 뜻한다.
• 들어오는 모든 요청은 요청 목록에 올라간다. 화물 무게 이상을 실을 수 있는 유휴 상태의 운송 로봇이 있으면 그 요청은 처리 가능하다.
• 목록에 처리 가능한 요청이 있는 한(그리고 생기는 즉시), 오래된 요청을 우선해 운송 로봇에 배정한다. 각 요청은 화물을 실을 수 있는 유휴 상태의 운송 로봇 중, 출발지에 반시계 방향으로 가장 가까운(즉, 시계 방향 이동 거리가 가장 짧은) 로봇에게 배정된다. 거리가 같은 로봇이 둘 이상이면 번호가 작은 로봇이 배정받는다. 배정된 요청은 목록에서 삭제된다.
• 배정은 즉시 이루어진다. 로봇은 요청을 배정받는 즉시 이동을 시작하고, 하역(화물 내리기)을 마치는 즉시 유휴 상태가 되어 새 요청을 받을 수 있다.

시각 0에는 모든 운송 로봇이 유휴 상태이며 포트 1번에 위치한다.

입력은 수행해야 할 여러 개의 시뮬레이션으로 이루어진다. 각 시뮬레이션은 두 정수 n과 m이 담긴 줄로 시작하며, 각각 포트의 수와 운송 로봇의 수를 뜻하고 2 ≤ n ≤ 100, 1 ≤ m ≤ 20을 만족한다. 이어지는 m개의 줄에는 각각 정수 l_i가 담기며, 이는 운송 로봇 i가 실을 수 있는 최대 적재량(은하 톤)이다.

그 뒤에는 하나 이상의 운송 요청이 이어진다. 각 요청은 네 정수 t, o, d, w가 담긴 줄로, 요청이 들어온 시각 t(시뮬레이션 시작부터의 분 단위), 출발 포트 o, 도착 포트 d, 그리고 컨테이너의 무게 w(은하 톤)를 뜻한다. 한 시뮬레이션 안에서 요청 시각은 엄격히 증가한다. 값은 1 ≤ t, 1 ≤ o, d ≤ n, o ≠ d, 그리고 1 ≤ w ≤ max{ l_i : 1 ≤ i ≤ m }를 만족한다. 요청 목록은 “-1 -1 -1 -1” 줄로 끝난다.

입력은 첫 줄이 “0 0”인 시뮬레이션으로 끝난다. 이 시뮬레이션은 처리하지 않는다.

각 시뮬레이션에 대해 먼저 “Simulation X” 줄을 출력한다. 여기서 X는 1부터 세는 시뮬레이션 번호이다. 그다음 아래 형식으로 정확히 두 줄을 출력한다.

Average wait time   = A minutes
Average utilization = B %

A는 모든 요청에 대한 평균 대기 시간이며, 한 요청의 대기 시간은 요청이 들어온 시각부터 화물이 배달될(하역이 끝나는 순간) 때까지의 시간이다. B는 첫 요청이 들어온 순간부터 마지막 요청이 배달되는 순간까지의 구간에 대한 가동률(%)로, 그 구간 동안 작업 중인 운송 로봇의 평균 개수를 m으로 나눈 뒤 100을 곱한 값이다.

A와 B는 모두 소수점 아래 세 자리까지 정확히 출력하며, 위에 보인 간격(띄어쓰기)을 그대로 따른다. 연속된 시뮬레이션의 출력 사이에는 빈 줄을 하나 넣는다.