#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>10000||K<0||K>N){
        printf("Invalid input");
        return 0;
    }
    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");
            return 0;
        }
        if(ids[id%MAX]!=0){
            printf("Invalid input");
            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");
        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;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");
            return 0;
        }
    }
    qsort(stocks,N,sizeof(Stock),compare);
    for(int i=0;i<K;i++){
        printf("%d ",stocks[i].id);
    }
    printf("\n");
    return 0;
}