#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) {
    const Stock s1 = (const Stock)a;
    const Stock s2 = (const 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 > MAX || K < 0 || K > N) {
        printf("Invalid 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].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\n");
        return 0;
    }
    for (int i = 0; i < U; i++) {
        int uid, newprice;
        if (scanf("%d %d", &uid, &newprice) != 2 || uid < 0 || newprice < 0) {
            printf("Invalid input\n");
            return 0;
        }
        int found = 0;
        for (int j = 0; j < N; j++) {
            if (stocks[j].id == uid) {
                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;
}