재생목록 사이의 안내 방송

문제

한 음악 스트리밍 서비스가 작은 공연장의 대기 공간에서 재생할 목록을 준비했다. 목록에는 N개의 곡이 들어 있으며, 각 곡의 재생 시간은 초 단위의 양의 정수로 주어진다. 재생은 첫 번째 곡의 시작과 함께 시작되고, 정해진 순서대로 모든 곡을 한 번씩 재생한다. 곡을 건너뛰거나 반복하지 않으며, 재생 중에 이용자가 일시 정지하는 일도 없다. 담당자는 마지막 곡이 끝날 때까지 걸리는 전체 시간을 미리 표시하려 한다. 이 서비스는 곡 사이에 짧은 안내 방송을 넣는다. 정확히 K개의 곡이 끝날 때마다 길이가 A초인 안내 방송을 한 번 재생한 뒤 다음 곡을 시작한다. 따라서 안내 방송이 들어갈 수 있는 위치는 K번째 곡 뒤, 2K번째 곡 뒤, 3K번째 곡 뒤와 같이 정해진다. 다만 마지막 곡 뒤에는 이어서 재생할 곡이 없으므로 안내 방송을 넣지 않는다. 마지막 곡의 순서가 K의 배수인 경우에도 이 예외를 적용한다. A가 0이면 안내 방송 때문에 늘어나는 시간은 없다. 곡 사이에는 정해진 안내 방송 외에 추가 대기 시간이 없다. 서로 다른 곡의 재생 시간이 같아도 각각 독립된 한 곡으로 센다. 전체 재생 시간은 모든 곡의 재생 시간과 실제로 들어가는 안내 방송 시간을 더한 값이다. 이 시간을 분과 초로 나누어 표시한다. 초 부분은 항상 0 이상 59 이하가 되어야 하며, 분 부분이 60 이상이 되더라도 시간 단위로 다시 바꾸지 않는다. 주어진 재생목록을 끝까지 재생하는 데 걸리는 시간을 계산한다.

입력

첫째 줄에 곡의 수 N, 안내 방송 간격 K, 안내 방송 길이 A가 공백으로 구분되어 주어진다. 둘째 줄에 첫 번째 곡부터 N번째 곡까지의 재생 시간 D1, D2, ..., DN이 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000, 0 ≤ A ≤ 120, 1 ≤ Di ≤ 600이다.

출력

전체 재생 시간이 M분 S초일 때 M과 S를 공백으로 구분하여 출력한다. M은 음이 아닌 정수이고 0 ≤ S < 60이다. 두 수에 불필요한 앞자리 0을 붙이지 않는다.

5 2 15
60 80 100 120 140

8 50

1 1 120
59

0 59

4 2 10
30 30 30 30

2 10

출처: Devin.KR 자체 제작