#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using Pii = pair<int,int>;

int ri() { int x; scanf("%d",&x); return x; }
ll rll() { ll x; scanf("%lld",&x); return x; }

void print(int x) { printf("%d",x); }
void print(ll x) { printf("%lld",x); }

template<class T> void remin(T& var, T x) { var = min(var,x); }
template<class T> void remax(T& var, T x) { var = max(var,x); }


#define REP(i,n) for(int i=0; i<int(n); ++i)
#define PER(i,n) for(int i=(n)-1; i>=0; --i)
#define ALL(c) (c).begin(), (c).end()



ll randll() {
	ll r = 0;
	REP(i,5) {
		r ^= rand();
		r <<= 15;
	}
	return abs(r);
}

ll rand(ll a, ll b) {
	return a + randll()%(b-a);
}

#define DBG false






struct Tree {

	Tree() {}
	Tree(int val) : value(val) {}
	Tree(int val, Tree* lll, Tree* rr) : value(val), l(lll), r(rr) {}

	Tree* persistent_set(int x, int val,   int this_a, int this_b) {
		if(this_a + 1 == this_b) {
			return new Tree(val);
		}

		int this_m = (this_a + this_b) / 2;

		auto new_l = l;
		auto new_r = r;

		if(x >= this_m) {
			if(!r) r = new Tree();
			new_r = r->persistent_set(x, val,   this_m, this_b);
		}
		else {
			if(!l) l = new Tree();
			new_l = l->persistent_set(x, val,   this_a, this_m);
		}

		auto new_val = INT_MAX;
		if(new_l) remin(new_val, new_l->value);
		if(new_r) remin(new_val, new_r->value);

		return new Tree(new_val, new_l, new_r);
	}

	int get_value(int a, int b,   int this_a, int this_b) {
		if(a >= b) return INT_MAX;

		if(this_a + 1 == this_b) return value;

		if(a <= this_a && this_b <= b) {
			return value;
		}

		int this_m = (this_a + this_b) / 2;

		int result = INT_MAX;

		if(l && a < this_m) {
			remin(result, l->get_value(a,b,   this_a, this_m));
		}

		if(r && this_m < b) {
			remin(result, r->get_value(a,b,   this_m, this_b));
		}

		return result;
	}

private:
	int value = INT_MAX;
	Tree* l = nullptr;
	Tree* r = nullptr;
};





struct Segment {
	int y0 = 0;
	int y1 = 0;
	int val = 0;
};


int num_pomiary = 0;
int num_dzieci = 0;

struct ByPos {
	vector<Segment> segments;
	Tree* tree = nullptr;
};

vector<ByPos> by_pos;



vector<int> result;

int TREE_SIZE = 0;

void solve(int pos,   int a, int b) {

	if(DBG) if(pos < 500) fprintf(stderr, "solve(%d,   %d, %d)\n", pos, a, b);

	if(a+1 == b || pos >= num_pomiary) {
		for(int i=a; i<b; ++i) result.push_back(i);
		return;
	}

	auto fr = upper_bound(ALL(by_pos[pos].segments), a, [](int aa, const Segment& s) {
		return aa < s.y0;
	});
	--fr;

	auto to = lower_bound(ALL(by_pos[pos].segments), b, [](const Segment& s, int bb) {
		return s.y0 < bb;
	});

	vector<Segment> segments(fr, to);

	stable_sort(ALL(segments), [&](const Segment& aa, const Segment& bb){
		return aa.val < bb.val;
	});

	for(auto& s : segments) {
		remax(s.y0, a);
		remin(s.y1, b);

		// find next pos

		int next_pos = by_pos[pos].tree->get_value(s.y0+1, s.y1,   0, TREE_SIZE);
		//int next_pos = pos+1;

		if(DBG) if(pos < 500) fprintf(stderr,"rect range from pos %d, (%d,%d) -> %d\n", pos, s.y0, s.y1, next_pos);

		solve(next_pos,   s.y0, s.y1);
	}
}



vector<int> pomiary;
vector<Pii> zmiany;

void read_input() {
	num_pomiary = ri();
	num_dzieci = ri();

	REP(i, num_pomiary) pomiary.push_back( ri() );

	REP(i, num_dzieci-1) {
		int pos = ri() - 1;
		int val = ri();
		zmiany.push_back({pos,val});
	}
}


void test_random() {
	num_pomiary = 500000;
	num_dzieci = 500000;

	REP(i, num_pomiary) pomiary.push_back( rand() % (1 * 1000 * 1000 * 1000) );

	REP(i, num_dzieci-1) {
		int pos = rand() % num_pomiary;
		int val = rand() % (1 * 1000 * 1000 * 1000);
		zmiany.push_back({pos,val});
	}
}



int main() {

	fprintf(stderr, "RAND_MAX == %d\n", RAND_MAX);

	read_input();
	//test_random();

	TREE_SIZE = num_dzieci + 10;

	by_pos.resize(num_pomiary);


	REP(i, num_pomiary) {
		Segment s;
		s.y0 = 0;
		s.val = pomiary[i];
		by_pos[i].segments.emplace_back( std::move(s) );
	}
	vector<int>().swap( pomiary ); // clear to save memory


	REP(i, num_dzieci-1) {

		Segment s;
		int pos = zmiany[i].first;
		s.y0 = i+1;
		s.val = zmiany[i].second;

		by_pos[pos].segments.back().y1 = s.y0;

		by_pos[pos].segments.emplace_back( std::move(s) );
	}

	REP(pos, num_pomiary) {
		by_pos[pos].segments.back().y1 = num_dzieci;
	}

	Tree* curr_tree = new Tree();

	fprintf(stderr, "build trees...\n");

	PER(i, num_pomiary) {
		for(auto& segment : by_pos[i].segments) {
			if(segment.y0 == 0) continue;

			curr_tree = curr_tree->persistent_set(segment.y0, i,   0, TREE_SIZE);
		}
		by_pos[i].tree = curr_tree;
	}

	fprintf(stderr, "solve...\n");

	solve(0,   0, num_dzieci);

	//if(DBG) assert(num_dzieci == (int)result.size());

	REP(i, result.size()) {
		printf("%d ", result[i] + 1);
	}
	puts("");

	return 0;
}