항공권 용지 보충

문제

공항의 항공권 발급기 한 대가 예약 순서대로 종이 항공권을 출력한다. 항공권 한 장을 출력할 때마다 용지 한 장을 사용하며, 한 예약에 필요한 항공권은 반드시 한 번에 모두 출력한다. 발급기는 처음에 용지 S장을 가지고 있고, 앞으로 처리할 예약은 N개다. i번째 예약에는 항공권 A_i장이 필요하다. 직원은 각 예약을 처리하기 직전에 발급기에 남은 용지를 확인한다. 남은 용지가 그 예약에 필요한 장수보다 적으면 새 묶음 하나를 넣는다. 새 묶음에는 항상 용지 R장이 들어 있으며, 기존에 남아 있던 용지를 버리지 않고 새 용지를 더한다. 따라서 보충 직후의 용지 수가 R장보다 많아질 수도 있다. 발급기의 용지함에는 이 과정에서 생기는 용지를 모두 넣을 수 있다. 용지를 확인하고 필요한 보충을 마친 다음에는 해당 예약의 항공권을 모두 출력한다. 출력에 사용한 장수만큼 남은 용지가 줄어든다. 모든 예약에서 필요한 장수는 R 이하이므로, 한 예약을 처리하기 위해 새 묶음을 두 번 이상 넣을 일은 없다. 남은 용지가 필요한 장수와 정확히 같을 때에는 보충하지 않고 그대로 출력한다. 예약은 입력에 주어진 순서대로 처리하며, 순서를 바꾸거나 여러 예약을 하나로 합치지 않는다. 직원은 용지가 부족한 경우에만 새 묶음을 넣는다. 예약 처리 도중이나 마지막 예약을 마친 뒤에는 용지를 추가로 보충하지 않는다. 처음부터 들어 있던 S장은 보충 횟수에 포함하지 않는다. 발급기 관리자는 다음 근무자에게 실제 보충 횟수와 남은 용지 수를 전달하려 한다. 모든 예약을 처리하는 동안 새 묶음을 넣은 횟수와, 마지막 항공권까지 출력한 직후에 발급기에 남아 있는 용지 장수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, R, S가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ R ≤ 1,000, 0 ≤ S ≤ R이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ A_i ≤ R이다.

출력

새 용지 묶음을 넣은 횟수와 모든 예약을 처리한 뒤 남은 용지 장수를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 보충하지 않았다면 횟수는 0을 출력하며, 용지가 남지 않았다면 남은 장수는 0을 출력한다.

5 8 3
3 5 4 8 2

3 5

3 10 10
2 3 5

0 0

1 6 0
6

1 0

출처: Devin.KR 자체 제작