34726번 - DRS

문제

2010년, F덕트라는 기술이 등장하여 레이스카의 다운포스를 줄임으로써 최고 속도를 향상시킬 수 있게 되었다.

그러나 국제자동차연맹(FIA)은 안전상의 이유로 이 기술을 금지하였고, 2011년부터는 이를 대체하는 기술인 DRS(Drag Reduction System) 를 도입하였다.

DRS는 레이스카의 리어윙을 조작해 다운포스를 줄이는 장치이다.

이 문제에서는 규칙을 단순화하여, 아래 조건일 때 DRS 사용이 가능하다.

1. 각 드라이버는 바로 앞 차량과의 거리 차이가 0 초과 1000 이하일 경우 트랙 어디에서나 DRS를 사용할 수 있다.
2. 랩 차이가 있어도 바로 앞차와의 실제 거리 차이가 이 범위면 DRS를 사용할 수 있다.

트랙은 길이 $T$의 원형이며, 모든 드라이버는 동일한 방향으로 트랙을 따라 주행한다.

예를 들어, $N$이 4ドル$이고, $T$가 60000ドル$인 원형 트랙에서 경기하고 있다고 생각하자. 레이스를 하는 드라이버의 이름은 $A,ドル $B,ドル $C,ドル $D$이고, 각각 1ドル,ドル 2ドル,ドル 3ドル,ドル 4ドル$등이라고 생각하자.

이 경우에, $B$는 $A$보다 30000ドル$ 만큼, $C$는 $B$보다 29000ドル$ 만큼, $D$는 $C$보다 1500ドル$만큼 뒤쳐져 있다고 하자.

$A$를 기준으로 $B$는 30000ドル$만큼, $C$는 59000ドル$만큼, $D$는 60500ドル$만큼 뒤쳐져 있다.

이때 물리적으로 $D$는 바로 앞 차량인 $A$에게서 500ドル$만큼 뒤에 있을 것이다.

DRS의 사용 조건에서, 0ドル$ 초과 1000ドル$ 이하의 간격인 상황이라면 DRS를 사용할 수 있기 때문에, $A$는 $C$보다 1000ドル$ 만큼 뒤에 있으므로 DRS를 사용할 수 있고, $D$는 $A$보다 500ドル$ 만큼 뒤에 있기 때문에 DRS를 사용할 수 있다. 그렇기 때문에 DRS를 사용할 수 있는 드라이버는 $A$와 $D$이다.

예시를 참고하여 각 드라이버가 DRS를 사용할 수 있는지 여부를 판단해보자.

입력

첫째 줄에 드라이버 수 $N$과 트랙 한 바퀴의 길이 $T$가 주어진다. $(2 \leq N \leq 200,000円 ; 1,000円 \leq T \leq 3,000円,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐, 순위가 높은 드라이버부터 차례대로 드라이버 이름 $D_i$와 바로 앞 등수와의 거리 차이 $t_i$가 주어진다. 거리는 앞 등수와의 상대적인 거리다. 가장 선두에 있는 드라이버는 앞에 차량이 없으므로, $t_1 = 0$ 임이 보장된다. 또한, 두 대 이상의 차가 같은 위치에 존재하지 않음이 보장된다.

출력

DRS를 사용할 수 있는 드라이버들의 이름을 사전순으로 출력한다.

DRS를 사용할 수 있는 드라이버가 없다면 -1을 출력한다.

제한

• 드라이버 이름은 영문 대소문자로 이루어진 공백 없는 문자열이며, 길이는 20ドル$ 이하이다. (서로 다른 두 드라이버의 이름이 같은 경우는 주어지지 않는다.)
• 0ドル \le t_i \leq 3,000円,000円$

노트

2025년은 DRS를 사용하는 마지막 해이다. 2026년부터는 새로운 기능으로 대체될 예정이다.