호텔의 숙박 기록판

문제

한 호텔은 객실이 실제로 사용된 정도를 알아보기 위해 매일 밤 사용 중인 객실 수를 기록한다. 운영자는 이 기록을 날짜순으로 더하여 누적 객실박 수를 관리한다. 객실박 하나는 객실 하나가 하룻밤 동안 사용되었다는 뜻이다. 같은 객실이 여러 밤 연속으로 사용되면 매일 밤 각각 하나씩 센다. 한 객실에 머무는 손님 수는 계산에 영향을 주지 않는다. 호텔에는 총 R개의 객실이 있으며, N일 동안의 기록을 확인하려고 한다. 관찰을 시작하기 전의 누적 객실박 수는 0이다. i일째 밤에 사용 중인 객실이 A개라면 그날 기록을 반영한 누적 객실박 수는 전날까지의 누적값에 A를 더한 값이다. 사용 중인 객실이 없는 날에는 누적값이 늘어나지 않는다. 모든 기록은 해당 날짜의 밤이 끝난 뒤 한 번만 반영한다. 운영자는 누적 객실박 수에 대한 목표 T를 정해 두었다. 날짜는 관찰 첫날을 1일째로 하여 순서대로 센다. 어떤 날의 기록을 반영한 누적값이 T 이상이면 그날 목표에 도달한 것으로 본다. 정확히 T가 된 경우도 포함한다. 목표에 여러 날 도달해 있더라도 처음 도달한 날짜 하나만 보고한다. 목표를 넘겼다고 해서 그 이후의 기록을 계산에서 제외하지는 않는다. 예를 들어 첫날과 둘째 날의 사용 객실 수가 각각 3개와 4개이고 목표가 6객실박이면, 첫날의 누적값은 3이고 둘째 날의 누적값은 7이므로 처음 도달한 날짜는 2이다. 날짜순 기록이 주어질 때, N일 전체의 객실박 수와 목표에 처음 도달한 날짜를 구한다. 마지막 날까지 목표에 도달하지 못하면 날짜 대신 0을 사용한다.

입력

첫째 줄에 정수 N, R, T가 공백으로 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ R ≤ 1,000, 1 ≤ T ≤ 1,000,000이다.
둘째 줄에 날짜순으로 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 0 ≤ A_i ≤ R이며 A_i는 i일째 밤에 사용 중인 객실 수이다.

출력

N일 전체의 객실박 수와 목표에 처음 도달한 날짜를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 목표에 도달한 날짜가 없으면 두 번째 값으로 0을 출력한다.

4 5 7
2 0 5 1

8 3

3 4 10
1 4 2

7 0

3 2 2
2 0 2

4 1

출처: Devin.KR 자체 제작