#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1000
typedef struct{
    int id;
    int initial;
    int current;
    int change;
}Stock;
int compare(const void*a,const void*b){
    Stock*s1=(Stock*)a;
    Stock*s2=(Stock*)b;
    if(s2->change==s1->change){
        return(s1->change){
            return s1->id-s2->id;
        }
        return s1->change-s1->change;
    }
    int main(){
        int N,K;
        if(scanf("%d %d",&N,&K)!=2||N<1||N>1000||K<0||K>1){
            printf("Invalid input\n");
            return 0;
        }
        if(ids[id%MAX]!=0){
            printf("Invalid input\n");
            return 0;
        }
        stocks[i].id=id;
        stocks[i].initial=price;
        stocks[i].current=price;
        stocks[i].change=0;
        ids[id%MAX]=1;
    }
    int U;
    if(scanf("%d",&U)!=1||U<0){
        printf("Invalid input\n");
        return 0;
    }
    for(int i=0;i<U;i++){
        int id,newPrice;
        if(scanf("%d %d",&id,&newPrice)!=2||newPrice<0){
            printf("Invalid input\n");
            return 0;
        }
        int found=0;
        for(int j=0;j<N;j++){
            if(stocks[j].id==id){
                stocks[j].current=newPrice;
                stocks[j].change=abs(stocks[j].current-stocks[j].initial);
                found==1;
                break;
            }
        }
        if(!found){
            printf("Invalid input\n");
            return 0;
        }
    }
    qsort(stocks,N,sizeof(Stock),compare);
    for(int i=0;i<K;i++){
        printf("%d",stocks[i].id);
    }
    printf("\n");
    return 0;
}