관측값이 남아 있는 시간

문제

날씨 관측소는 여러 센서가 보내는 기온 기록을 모아 현황판을 만든다. 기록 하나에는 관측 시각 t, 센서 번호 s, 정수 기온 v가 들어 있다. 통신 지연 때문에 파일에 적힌 순서와 관측 시각의 순서가 다를 수 있다. 현황판은 파일을 모두 받은 뒤 관측 시각이 빠른 순서대로 과거의 상태를 복원한다. 같은 센서에서 새 기록을 관측하면 그 센서의 이전 기록은 즉시 교체된다. 이전 기록은 이후에 다시 사용할 수 없다. 하나의 센서에 같은 관측 시각의 기록이 여러 개 있으면 입력 파일에서 더 뒤에 적힌 기록 하나만 채택한다. 서로 다른 센서의 기록은 각각 독립적으로 관리한다. 같은 시각에 도착한 것으로 처리되는 기록은 모두 반영한 다음 현황판을 확인한다. 기록의 유효 기간은 모든 센서에 대해 D로 같다. 시각 a에 관측한 기록은 a ≤ x < a+D인 시각 x에서만 유효하다. 따라서 현황판을 확인하는 시각이 정확히 a+D라면 해당 기록은 이미 만료된 상태다. 센서의 가장 최근 기록이 만료되면 그 센서는 유효한 관측값을 갖지 않는다. 교체되어 사라진 과거 기록을 찾아 대신 사용하는 일은 없다. 파일에 등장하는 서로 다른 관측 시각마다 한 번씩 현황판을 출력한다. 각 시각에서는 그 시각의 기록 교체와 만료 처리를 모두 끝낸 상태를 기준으로 한다. 출력할 정보는 현재 유효한 관측값을 가진 센서의 수, 그중 가장 높은 기온, 그리고 그 기온을 기록한 센서 번호다. 가장 높은 기온을 가진 센서가 여러 개라면 번호가 가장 작은 센서를 선택한다. 입력에 등장하지 않는 중간 시각의 현황판은 출력하지 않는다. 모든 관측 시각에는 적어도 하나의 새 기록이 있고 D는 양수이므로, 출력 시점에는 항상 유효한 센서가 하나 이상 존재한다. 기온은 음수일 수도 있으며, 이 경우에도 일반적인 정수의 대소 관계에 따라 최고 기온을 정한다.

입력

첫째 줄에 정수 N과 D가 주어진다. 1 ≤ N ≤ 10,000, 1 ≤ D ≤ 1,000,000이다.
다음 N개 줄에 정수 t, s, v가 주어진다. 0 ≤ t ≤ 1,000,000, 1 ≤ s ≤ 200,000, -100 ≤ v ≤ 100이다.
기록은 임의의 순서로 주어지며, 동일한 t와 s가 반복될 수 있다.

출력

입력에 등장하는 서로 다른 관측 시각을 오름차순으로 처리한다. 각 시각마다 시각, 유효한 센서 수, 최고 기온, 선택한 센서 번호를 공백으로 구분하여 한 줄에 출력한다.

5 5
7 1 -2
1 2 4
1 1 4
4 2 9
6 3 9

1 2 4 1
4 2 9 2
6 2 9 2
7 3 9 2

3 1
0 3 -5
0 3 -7
2 4 -100

0 1 -7 3
2 1 -100 4

출처: Devin.KR 자체 제작