#include<stdio.h>
#include<stdlib.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->id-s2->id;
    }
    return s2->change-s1->change;
}
int main(){
    int N,K;
    if(scanf("%d,%d",&N,&K)!=2||N>1000||K<0||K>N){
        printf("Invalid input\n");
    }
    Stock stock[MAX];
    int ids[MAX]={0};
    for(int i=0;i<N;i++){
        int id,price;
        if(scanf("%d,%d",&id,&price)!=2||id<0||price<0){
            printf("Invalid input\n");
            return 0;
        }
        if(ids[id%MAX]!=0){
            printf("Invalid input\n");
            return 0;
        }
        stock[i].id=id;
        stock[i].initial=price;
        stock[i].current=price;
        stock[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 fuond=0;
    for(int j=0;j<N;j++){
        if(stocks[j].id==id){
            stocks[j].current=newPrice;
            stocks[j].change=ads(stocks[j].current-stocks[j].initial);
            found =1;
            break;
        }
    }
    if(!fuond){
     printf("Invalid input\n");
     return 0;
    }
}
qsort(stock,N,sizeof(Stock),compare);
for(int i=0;i<k;i++){
    printf("%d",stock[i].id);
}
printf("\n");
return 0;
}