#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ALL(u) (u).begin(),(u).end()

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

typedef pair<int, int> PII;

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

const int MR = 5e5 + 10;

const int pr = 70032301, q = 1000000007;

// persistent segment tree
struct node
{
	int v;
	int p, k;

	node *left, *right;
};

node *tree[MR];

int t[MR], potp[MR];

int p, k, v;
void build(node *root, int p, int k)
{

	root->p = p;
	root->k = k;

	if (p < k)
	{
		if (root->left == NULL)
			root->left = new node();
		build(root->left, p, (p + k) / 2);

		if (root->right == NULL)
			root->right = new node();
		build(root->right, (p + k) / 2 + 1, k);

		root->v = (root->left->v + root->right->v*(LL)potp[root->left->k - root->left->p + 1]) % q;

		return;
	}

	root->v = t[p - 1];
}

// zwroc hasz na danym przedziale
int ans(node *root)
{
	if (root->p > k || root->k < p)
		return 0;
	if (root->p < p || root->k > k)
	{
		int vl = ans(root->left);
		int vr = ans(root->right);

		if (vr && root->left->k >= p)
			vr = vr*(LL)potp[root->left->k - p + 1] % q;
		return vl + vr;
	}

	return root->v;
}



// przed modyfikacja musisz wstawic segment tree dla nowego wierzcholka
node* insert(node *root)
{
	// if out of range, return this node
	if (root->k < p || root->p > p)
		return root;

	node *res = new node();

	res->p = root->p;
	res->k = root->k;
	res->v = root->v;

	if (root->p < root->k)
	{
		res->left = insert(root->left);
		res->right = insert(root->right);
	}

	return res;
}

void addNew(int nr, int par)
{
	tree[nr] = insert(tree[par]);
}

void modify(node *root)
{
	if (root->p > p || root->k < p)
		return;
	if (root->p < p || root->k > p)
	{
		modify(root->left);
		modify(root->right);

		root->v = (root->left->v + root->right->v*(LL)potp[root->left->k - root->left->p + 1]) % q;

		return;
	}

	root->v = v;
}

//int verRes;
//void verify(node *root)
//{
//	if (root->k < p || root->p > p)
//		return;
//	if (root->p < p || root->k > p)
//	{
//		verify(root->left);
//		verify(root->right);
//		return;
//	}
//
//	verRes = root->v;
//
//}

//bool check(int v1, int v2, int k)
//{
//	vector<int> pos;
//	REP(i, 5)
//		pos.push_back(rand()*(LL)rand() % k + 1);
//
//	for (int i : pos)
//	{
//		p = i;
//		verify(tree[v1]);
//		int prev = verRes;
//		verify(tree[v2]);
//		if (prev != verRes)
//			return 0;
//	}
//
//	return 1;
//}

int n;
int find(const node *t1, const node *t2)
{
	// zwroc pierwszy indeks, na ktorym rozni sie hash
	if (t1->v == t2->v)
		return t1->k + 1;

	if (t1->p == t1->k)
		return t1->p;

	int left = find(t1->left, t2->left);

	if (left <= t1->left->k)
		return left;

	return find(t1->right, t2->right);
}

inline bool cmp(const int &i1, const int &i2)
{
	int ind = find(tree[i1], tree[i2]);
	//printf("cmp %d %d, roznia sie na pos: %d\n", i1, i2, ind);
	// jesli hasze sa takie same, to posortuj po numerach
	if (ind > n)
		return i1 < i2;

	p = k = ind;

	int v1 = ans(tree[i1]), v2 = ans(tree[i2]);
	return v1 < v2;
}

int srt[MR], cp[MR];

void mergesort(int p, int k)
{
	if (p >= k - 1)
		return;
	if (p == k - 2)
	{
		if (cmp(srt[p + 1], srt[p]))
			swap(srt[p + 1], srt[p]);
		return;
	}

	int half = (p + k) / 2;
	mergesort(p, half);
	mergesort(half, k);

	int b1 = p, b2 = half, wsk = 0;

	while (b1 < half && b2 < k)
		if (cmp(srt[b1], srt[b2]))
			cp[wsk++] = srt[b1++];
		else
			cp[wsk++] = srt[b2++];

	while (b1 < half)
		cp[wsk++] = srt[b1++];
	while (b2 < k)
		cp[wsk++] = srt[b2++];

	REP(i, wsk)
		srt[p + i] = cp[i];
}

int main()
{
	/*n = 5e5;
	int m = 5e5;

	REP(i, n)
	t[i] = rand()*(LL)rand() % 1000000000 + 1;*/

	int m;
	scanf("%d%d", &n, &m);
	REP(i, n)
	{
		scanf("%d", &t[i]);
		t[i]++;
	}

	potp[0] = 1;
	FORQ(i, 1, n)
		potp[i] = (potp[i - 1] * (LL)pr) % q;

	int sz = 1;
	while (sz < n)
		sz *= 2;
	tree[0] = new node();
	build(tree[0], 1, sz);

	FOR(i, 1, m)
	{
		scanf("%d%d", &p, &v); v++;
		/*p = rand()*(LL)rand() % n + 1;
		v = rand()*(LL)rand() % 1000000000 + 1;*/
		addNew(i, i - 1);
		modify(tree[i]);
		srt[i] = i;
	}

	/*REP(i, 500000)
	{
	p = rand()*(LL)rand() % n + 1;
	k = rand()*(LL)rand() % n + 1;
	int id1 = rand()*(LL)rand() % m;
	int id2 = rand()*(LL)rand() % m;
	if (p > k)
	swap(p, k);
	ans(tree[id1]);
	BS(id1, id2);
	}*/

	mergesort(0, m);

	REP(i, m)
		printf("%d ", srt[i] + 1);
	printf("\n");

	return 0;
}