#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Point {
ll x, y, idx;
friend bool operator<(Point a, Point b) {
if(a.y != b.y) return a.y > b.y;
return a.x < b.x;
}
};
int base = 1<<17;
int inf = 1e9;
struct SegTree {
vector<int> T;
SegTree() {
T.assign(2*base, inf);
}
void update(int x, int val) {
x+=base;
T[x] = min(T[x], val);
x/=2;
while(x > 0) {
T[x] = min(T[x+x], T[x+x+1]);
x/=2;
}
}
int query(int a, int b) {
if(a>b) return inf;
if(a==b) return T[a+base];
a+=base-1;
b+=base+1;
int res = inf;
while(a/2 != b/2) {
if(a%2==0) res = min(res, T[a+1]);
if(b%2==1) res = max(res, T[b-1]);
a/=2; b/=2;
}
return res;
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
for(auto &x : a) cin >> x;
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
vector<Point> allP(n);
for(int i=0; i<n; ++i) {
cin >> allP[i].x >> allP[i].y;
allP[i].idx = i;
}
vector<int> lowest(n), edge(n);
vector<int> res(n, -1);
auto pkt = allP;
sort(pkt.begin(), pkt.end());
SegTree st;
for(auto[x,y,i] : pkt) {
edge[i] = st.query(0, y);
st.update(y, i);
if(edge[i] != inf) lowest[i] = lowest[edge[i]];
else lowest[i] = i;
}
auto tag = [&](int x, int y, int val) {
for(int i=0; i<n; ++i) {
if(allP[i].x <= x && allP[i].y >= y && res[i]==-1) res[i] = val;
}
};
auto obsluz = [&](int i, int val) {
tag(allP[i].x, allP[i].x, val);
tag(allP[i].y, allP[i].y, val);
};
// for(int i=0; i<n; ++i) cout << lowest[i] << " "; cout << "\n";
int curr = 0;
for(auto[x,y,i] : allP) {
if(res[i] != -1) continue;
obsluz(lowest[i], a[curr]);
curr++;
}
for(int i=0; i<n; ++i) cout << res[i] << "\n";
return 0;
}
