/*
    （1）按时间、编号排序
    （2）遍历时间段，开头和结尾
    （3）开头前进，开头和结尾距离大于要求就让结尾前进  像似队列操作

*/
import java.util.*;
public class Main{
    static int N=100010;
    static int n,d,k;
    static int cnt[]=new int[N];
    static boolean st[]=new boolean[N];
    static Pair p[]=new Pair[N];
    static class Pair implements Comparable<Pair>{
        int x,y;
        Pair(int x,int y){
            this.x=x;
            this.y=y;
        }
        public int compareTo(Pair o){
            if(this.x == o.x) return this.y-o.y; //双条件排序
            return this.x-o.x;
        }
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt(); d=sc.nextInt(); k=sc.nextInt();
        for(int i = 0; i < n; i++ ){
            int x=sc.nextInt();
            int y=sc.nextInt();
            p[i]=new Pair(x,y);
        }
        Arrays.sort(p,0,n); //排序可以去计算时间段区间大小
        for(int i=0,j=0;i<n;i++){
            cnt[p[i].y]++;
            while( p[i].x - p[j].x >= d ){  //长度短了就不变结尾 长度长了就让结尾前进
                cnt[p[j].y]--;
                j++;
            }
            if(cnt[p[i].y]>=k) st[p[i].y]=true; // 长度合适才能开始判断
        }
        for(int i=1;i<N;i++) if(st[i]) System.out.println(i);
    }
}

二刷复习：分别计算每个id的前缀和里区间长度<=d且总和值>=k的

import java.util.*;
import java.io.*;
public class Main{
    static int N = 100010, n, d, k;
    static Map<Integer, List<Integer>> map = new HashMap();
    static int res[] = new int[N], cnt;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        d = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        // len 在d以内的区间和>=k
        while(n -- != 0){
            s = br.readLine().split(" ");
            int ts = Integer.parseInt(s[0]);
            int id = Integer.parseInt(s[1]);
            if(map.get(id) == null){
                map.put(id, new ArrayList());
            }
            map.get(id).add(ts);
        }
        for(int id : map.keySet()){
            Collections.sort(map.get(id));
            // 判断是否是热帖
            if(check(map.get(id))) res[cnt ++] = id;
        }
        Arrays.sort(res, 0, cnt);
        for(int i = 0; i < cnt; i ++) bw.write(res[i]+"\n");
        bw.flush();

    }

    static boolean check(List<Integer> list){
        int s[] = new int[N];
        for(int ts : list){
            s[ts] ++;
        }
        for(int i = 1; i < N; i ++) s[i] = s[i-1] + s[i];  // 前缀和

        int q[] = new int[N];
        int hh = 0, tt = -1;
        for(int i = 0; i < N; i ++){
            if(hh <= tt && i-q[hh]+1 > d+1) hh ++;  // l-1  ~  r的区间长度>d+1不合法
            while(hh <= tt && s[q[tt]] >= s[i]) tt --;  // 维护单调性
            q[++ tt] = i;  
            if(s[q[tt]] - s[q[hh]] >= k) return true;  // 队尾就是 以i结尾长度不超过d+1的l-1最小值
        }
        return false;
    }
}