세탁소의 적립 도장

문제

한 세탁소는 손님이 맡긴 옷의 수만큼 도장을 적립하고, 도장 K개마다 할인권 한 장을 발급한다. 세탁소는 새 적립 행사를 시작한 날부터 N일 동안 한 손님의 이용 기록을 정리하려 한다. 행사 시작 직전에 이 손님이 가진 도장은 0개이며, 할인권을 발급하는 데 사용한 도장은 다시 사용할 수 없다. 각 날짜의 영업이 끝나면 그날 맡긴 옷의 수만큼 도장을 한꺼번에 추가한다. 이어서 남아 있는 도장이 K개 이상인 동안 도장 K개를 없애고 할인권 한 장을 발급하는 일을 반복한다. 따라서 하루에 할인권이 여러 장 발급될 수도 있다. 그날 할인권을 모두 발급한 뒤 남은 도장은 다음 날로 그대로 넘어간다. 옷을 한 벌도 맡기지 않은 날에도 날짜는 하루 지난 것으로 센다. 예를 들어 K가 7이고 전날까지 남은 도장이 5개일 때, 오늘 옷을 18벌 맡겼다면 도장은 모두 23개가 된다. 오늘 할인권 세 장을 발급하면서 도장 21개를 사용하므로, 다음 날로 넘어가는 도장은 2개다. 이전 날짜에 발급한 할인권은 오늘 발급한 장수에 포함하지 않는다. 세탁소가 알고 싶은 것은 할인권을 가장 많이 발급한 날짜와 그날 발급한 장수다. 날짜는 행사 첫날을 1일로 하여 차례대로 번호를 붙인다. 가장 많은 장수를 발급한 날짜가 여러 개라면 가장 이른 날짜를 고른다. 단, N일 동안 할인권을 한 장도 발급하지 않았다면 고른 날짜와 그날의 장수를 모두 0으로 기록한다. 이 경우에도 마지막 날에 남은 도장은 따로 계산한다. N일 동안 매일 맡긴 옷의 수가 주어질 때, 위 규칙에 따라 고른 날짜, 그날 발급한 할인권의 장수, N일째 영업이 끝난 뒤 남은 도장의 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. N은 기록한 날짜 수이고 K는 할인권 한 장에 필요한 도장 수다. (1 ≤ N ≤ 30,000, 1 ≤ K ≤ 1,000,000,000)
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. A_i는 i일째 맡긴 옷의 수다. (0 ≤ A_i ≤ 10,000)
입력으로 주어지는 모든 수는 정수다.

출력

고른 날짜, 그날 발급한 할인권의 장수, 마지막에 남은 도장의 수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 할인권이 한 장도 발급되지 않았다면 앞의 두 수는 모두 0이다.

5 7
5 18 1 20 5

2 3 0

4 20
3 0 4 2

0 0 9

3 4
0 10 3

2 2 1

출처: Devin.KR 자체 제작