작업 \(n\)개가 큐에 들어 있다.

각 작업은 \(1\)번부터 \(n\)번까지 번호가 붙어 있으며, 처음에는 번호가 작은 작업이 앞에 있다.

한 번에 최대 \(q\)만큼의 시간만 작업을 처리할 수 있다.

가장 앞 작업을 꺼내 \(q\)만큼 처리한다.

작업이 끝나지 않았다면 남은 시간을 가지고 큐의 뒤로 다시 들어간다.

작업이 끝났다면 그 작업의 번호와 완료 시각을 기록한다.

모든 작업이 끝나는 순서를 출력하라.

입력

첫째 줄에 작업의 수 \(n\)과 시간 할당량 \(q\)가 공백으로 구분되어 주어진다.

둘째 줄에 각 작업에 필요한 시간 \(n\)개가 공백으로 구분되어 주어진다.

\((1 \le n \le 100000)\)

\((1 \le q \le 1000)\)

각 작업에 필요한 시간은 \(1\) 이상 \(1000\) 이하이다.

출력

작업이 끝나는 순서대로 작업 번호와 완료 시각을 한 줄에 하나씩 출력한다.

예제 입력

3 2
1 2 3

예제 출력

1 1
2 3
3 6

예제 설명

처음 큐에는 1번 작업(1), 2번 작업(2), 3번 작업(3)이 들어 있다.

시간 할당량은 \(2\)이다.

먼저 1번 작업을 처리한다. 필요한 시간이 \(1\)이므로 시각 \(1\)에 완료된다.

다음으로 2번 작업을 처리한다. 필요한 시간이 \(2\)이므로 시각 \(3\)에 완료된다.

다음으로 3번 작업을 처리한다. \(2\)만큼 처리하면 시각은 \(5\)가 되고, 3번 작업은 아직 \(1\)만큼 남아 큐의 뒤로 이동한다.

다시 3번 작업을 처리하면 시각 \(6\)에 완료된다.