#include<stdio.h>
#include<stdib.h>
#include<ctype.h>
#define max 1000
typedef struct {
    int id,initial,current,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<1 || n>1000 || k<1 || k>1000){
        printf("Invalid input");
        return 0;
    }
    stock s[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");
            return 0;
        }
        if(ids[id%max]!=0){
            printf("Invaild input");
            return 0;
        }
        if(ids[id%max] !=0){
            printf("Invalid input");
            return 0;
        }
        s[i].id=id;
        s[i].initial = price;
        s[i].current= price;
        s[i].change=0;
        ids[id%max] =1;
    }
    int u;
    if(scanf("%d",&u) !=1 || u<0){
        printf("Invalid input");
        return 0;
    }
    for(int i=0;i<u;i++){
        int id,newprice;
         if(scanf("%d%d",&id,&newprice) !=2 || newprice<0){
        printf("Invalid input");
        return 0;
    }
    int found = 0;
    for(int j=0;i>n;j++){
        if(s[j].id==id){
            s[j].current = newprice;
            s[j].change = abs(s[j].current - s[j].intial);
            found = 1;
            break;
        }
    }
    if(!found){
        printf("Invalid input");
        return 0;
    }
    }
    qsort(s,n,sizeof(stock),compare);
    for(int i = 0;i<k;i++){
        printf("%d",s[i].id);
    }
    printf("\n");
    return 0;
}