25604번 - 비행기 전시

문제

항공대에는 두 대의 비행기가 전시되어 있다. 현재 두 비행기는 각각 0ドル$번과 1ドル$번 위치에 전시되어 있다. 그리고 트럭이 한 비행기가 전시된 위치에서 다른 비행기가 전시된 위치로 가는데는 $T$의 시간이 소요된다. 항공대는 미관상의 이유로 두 비행기가 전시된 위치를 서로 바꾸려고 한다. 비행기는 매우 크기 때문에, 비행기를 옮기기 위해서는 비행기를 작은 부품들로 분해한 뒤 이를 재조립하는 방식을 사용한다. 양쪽 비행기에서 분해해 옮겨야 할 부품의 개수는 총 $N$개이며, 각 부품은 운송이 준비되는 순서대로 번호가 매겨진다. 그리고 부품을 옮기기 위한 트럭의 최대 적재량은 $M$이다.

현재 수업을 듣기 위해 많은 학생들이 캠퍼스 내에 있기 때문에 학교에서는 안전상의 문제로 트럭을 한 대만 운용하려고 한다. 이때 작업 시간을 단축하기 위해 한 번에 최대한 많은 무게를 트럭에 실으려 하는데, 트럭에 실을 수 있는 여유 공간에 비해 실으려는 부품의 크기가 큰 경우 부품을 더 분해해서 실을 수 있다. 예를 들어 트럭에 남은 여유 무게가 20ドル$이고, 부품의 무게가 50ドル$이라면, 부품을 20ドル$과 30ドル$으로 분해해서 20ドル$을 트럭에 싣고 출발한다.

반대편 비행기에 트럭이 도착할 경우, 트럭이 실은 부품을 모두 비운 후 트럭의 도착 시점에 운송이 준비된 부품들을 번호 순서대로 싣는다. 이때 부품을 싣고 내리는 시간은 고려하지 않는다. 준비된 부품을 최대한 실었다면 반대편으로 출발한다.

두 비행기에서 분해된 부품이 아직 운송이 준비되지 않은 경우도 존재할 수 있다. 이런 경우 하나의 부품이 준비될 때까지 기다리다가 부품이 먼저 준비된 쪽으로 이동한다. 이때, 양 비행기에서 다음으로 준비되는 부품의 시간이 동일하다면, 현재 트럭 위치의 부품을 먼저 싣는다. 만약, 현재 트럭이 있는 비행기가 모두 분해되었으면 반대쪽 비행기로 바로 이동해서 분해된 부품이 나올 때까지 대기한다.

당신은 각 부품이 언제 출발했고, 언제 도착했는지에 대한 시간을 기록하고 싶다. 각 부품이 나오는 비행기의 번호와 부품의 무게, 운송이 준비되는 시간이 주어질 때, 각 부품이 출발하고 도착하는 시간을 순서대로 출력하자. 단, 부품이 분해된 경우 출발 시간은 분해된 부품이 최초로 출발한 시간, 도착시간은 분해된 부품들이 모두 반대편에 완전히 도착했을 때의 시간이다.

입력

첫 번째 줄에 전체 부품의 수 $N,ドル 트럭의 최대 적재량 $M,ドル 두 비행기 간의 거리 $T$가 주어진다. (1ドル \le N \le 1,000円,ドル 1ドル \le M \le 1,000円,ドル 1ドル \le T \le 100$)

다음 $N$개의 줄에 $i$번 부품의 위치 $d_i,ドル 부품의 무게 $m_i,ドル 운송이 준비되는 시간 $r_i$이 주어진다. ($d \in \{0, 1\},ドル 1ドル \le m \le M,ドル 0ドル \le r \le 10,000円$)

모든 입력 케이스에서 $r_i$는 감소하지 않는 순서로 주어지며, 1ドル$번 부품은 항상 0ドル$번 위치에 있는 비행기의 부품이다. 주어지는 수는 모두 정수이다.

처음 트럭은 0ドル$번 위치에 있다.

출력

$N$개의 줄에 걸쳐 $i$번 부품의 출발 시간과 도착 시간을 공백으로 구분해 출력한다.

제한

힌트