Description

Xiaoming maintains a programmer forum. Now he has collected a set of "like" logs with a total of $N$ lines. Each line is in the format ts id, meaning that at time $ts$, the post with number $id$ received one "like".

Now Xiaoming wants to count which posts have ever been "hot posts". If a post has received at least $K$ likes within any time period of length $D$, Xiaoming considers that this post has once been a "hot post".

More specifically, if there exists a time $T$ such that the post receives at least $K$ likes during the time interval $[T, T + D)$ (note that it is a left-closed right-open interval), then this post has once been a "hot post".

Given the logs, please help Xiaoming list the IDs of all posts that have ever been "hot posts".

Input Format

The first line contains three integers $N$, $D$, and $K$.

The following $N$ lines each contain one log entry, with two integers $ts$ and $id$.

Output Format

Output the IDs of hot posts in increasing order. Print one $id$ per line.

7 10 2  
0 1  
0 10    
10 10  
10 1  
9 1
100 3  
100 3  

1  
3  

Hint

For $50\%$ of the testdata, $1 \le K \le N \le 1000$.

For $100\%$ of the testdata, $1 \le K \le N \le 10^5$, and $0 \le id, ts \le 10^5$.

Time limit: 1 second, 256 MB. Lanqiao Cup 2018, 9th Provincial Contest.

Translated by ChatGPT 5