#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

int main () {
    int N, A; cin >> N >> A;
    vector<int> X(N);
    for (int i = 0; i < N; i++) cin >> X[i];

    int T; cin >> T;

    enum ElementType {
        sound_begin,
        sound_end,
        person,
    };

    vector<tuple<int, int, int>> events(2*T + N);
    for (int t = 0; t < T; t++) {
        int L, R; cin >> L >> R;
        events[t] = make_tuple(L, t+1, sound_begin);
        events[T+t] = make_tuple(R+1, t+1, sound_end);
    }

    for (int i = 0; i < N; i++) events[2*T + i] = make_tuple(X[i], i, person);

    sort(events.begin(), events.end(),
            [](tuple<int, int, int> x, tuple<int, int, int> y) {
            if (get<0>(x) != get<0>(y)) return get<0>(x) < get<0>(y);
            if (get<2>(x) == person) return false;
            if (get<2>(y) == person) return true;
            return true; });

    vector<int> ans(N, -1);

    map<int, int> mp;

    for (auto& e : events) {
        if (get<2>(e) == person) {
            if (!mp.empty()) ans[get<1>(e)] = mp.rbegin()->first;
        }

        if (get<2>(e) == sound_begin) {
            mp[get<1>(e)] = 0;
        }

        if (get<2>(e) == sound_end) {
            mp.erase(get<1>(e));
        }
    }

    for (auto& v : ans) cout << v << "\n";
}