상영별 좌석 확인표

문제

한 영화관에서는 상영관에 들어오는 관객에게 좌석 확인표를 한 장씩 나누어 준다. 확인표는 여러 장이 이어진 묶음으로 보관하며, 모든 묶음에는 정확히 K장의 확인표가 들어 있다. 직원은 각 상영의 입장이 시작될 때 필요한 만큼 새 묶음을 뜯는다. 관객 한 명에게 확인표 한 장이 필요하므로, 해당 상영의 모든 관객에게 확인표를 줄 수 있을 만큼의 묶음을 준비해야 한다. 각 묶음에는 그 묶음을 뜯은 상영의 식별 도장을 찍는다. 따라서 어떤 상영에서 쓰고 남은 확인표는 다른 상영에 사용할 수 없다. 직원은 상영이 끝날 때 남은 확인표를 모두 따로 모으며, 다음 상영에서는 다시 새 묶음만 사용한다. 묶음을 뜯기 전에는 확인표를 낱장으로 꺼낼 수 없고, 한 번 뜯은 묶음을 새 묶음으로 되돌릴 수도 없다. 영화관에는 새 묶음이 충분히 있으므로 재고가 부족한 경우는 없다. 오늘은 총 N번의 상영이 예정되어 있고, 각 상영에 입장할 관객 수가 이미 확정되어 있다. 직원은 매 상영마다 뜯는 묶음 수가 가장 적도록 준비한다. 관객이 없는 상영에서는 묶음을 하나도 뜯지 않는다. 관객 수가 한 묶음의 확인표 수와 정확히 같다면 한 묶음만 뜯으며, 확인표가 한 장이라도 부족하면 새 묶음을 추가로 뜯어야 한다. 예를 들어 한 묶음에 6장이 있고 관객이 8명이라면 두 묶음을 뜯고, 그 상영이 끝난 뒤에는 4장이 남는다. 관리자는 하루 동안 뜯은 묶음의 총개수와, 각 상영이 끝난 뒤 남겨 둔 확인표의 총장수를 기록하려 한다. 남은 확인표에는 관객에게 나누어 준 확인표를 포함하지 않으며, 처음부터 뜯지 않은 묶음 속 확인표도 포함하지 않는다. 주어진 상영 순서대로 준비했을 때 관리자가 기록할 두 정수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 상영 횟수 N과 한 묶음에 들어 있는 확인표 수 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000이다.
둘째 줄에 각 상영의 관객 수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 A_i는 0 이상 1,000 이하의 정수이다.

출력

하루 동안 뜯은 묶음의 총개수와 각 상영이 끝난 뒤 남은 확인표의 총장수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 모든 상영의 관객 수가 0이면 두 값 모두 0을 출력한다.

4 6
8 0 6 13

6 9

3 5
0 0 0

0 0

5 4
1 4 5 8 1

7 9

출처: Devin.KR 자체 제작