#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->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<0 || K>N){
        printf("Ivalid input\n");
        return 0;
    }
    stock stocks[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;
        }
        stocks[i].id = id;
        stocks[i].intial = 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 fount = 0;
        for (int j=0; j<N; j++){
            if(stocks[j].id == id){
                stocks[j].current = newPrice;
                stocks[j].change = abs(stocks[j].currnt-stocks[j].initial);
                found = 1;
                break;
            }
        }
        if(!found){
            printf("Invalid input\n");
            return 0;
        }
    }
    qsort(storks,N,sizeof(stock),compare);
    for(int i=0; i<K; i++){
        printf("%d",storks[i].id);
    }
    print("\n");
    return 0;
}