#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 > 1000 || K < 0 || K > N) {
        printf("Invalid input\n");
        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\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 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;
}
    }
}