#include<iostream>

#include<vector>

using namespace std;



//升序函数

void acsceding(int* src, int low, int high)

{

	if (low < high)

	{

		int i = low, j = high, temp = src[low];

		while (i < j)

		{

			while ((i < j) && (src[j] >= temp))

			{

				j--;

			}

			if (i < j)

			{

				src[i++] = src[j];

			}



			while ((i < j) && (src[i] < temp))

			{

				i++;

			}

			if (i < j)

			{

				src[j--] = src[i];

			}

		}



		src[i] = temp;

		acsceding(src, low, i - 1);

		acsceding(src, i + 1, high);

	}

}

//降序函数

void desceding(int* src, int low, int high)

{

	if (low < high)

	{

		int i = low, j = high, temp = src[low];

		while (i < j)

		{

			while ((i < j) && (src[j] < temp))

			{

				j--;

			}

			if (i < j)

			{

				src[i++] = src[j];
			}



			while ((i < j) && (src[i] >= temp))

			{

				i++;

			}

			if (i < j)

			{

				src[j--] = src[i];

			}

		}



		src[i] = temp;

		desceding(src, low, i - 1);

		desceding(src, i + 1, high);

	}

}

//反序函数

void reverse(int* src, int len)

{

	int i = 0, j = len, temp;

	while (i < j)

	{

		temp = src[i];

		src[i++] = src[j];

		src[j--] = temp;

	}

}



int main()

{

	//1.读取输入数据

	int n, m;

	cin >> n >> m;



	int* src = new int[n];

	for (int i = 0; i < n; i++)

	{

		cin >> src[i];

	}



	vector<vector<int>> op(m, vector<int>(2));

	for (int i = 0; i < m; i++)

	{

		cin >> op[i][0] >> op[i][1];

	}

	//2.找到有效的排序命令

	int tempacs = op[0][1], tempacsloc = 0;

	int tempdes = op[0][1], tempdesloc = 0;

	for (int i = 1; i < m; i++) {

		if ((op[i][0] == 1) && (op[i][1] >= tempacs))

		{

			tempacs = op[i][1];

			tempacsloc = i;

		}

		else if ((op[i][0] == 2) && (op[i][1] >= tempdes))

		{

			tempdes = op[i][1];

			tempdesloc = i;

		}

	}



	//3.如果先升后降，升少降多则选降；先升后降，升多降少则先升后降；……

	if (tempacsloc > tempdesloc)

	{

		if (tempacs >= tempdes)

		{

			acsceding(src, 0, op[tempacsloc][1] - 1);

		}

		else {

			desceding(src, 0, op[tempdesloc][1] - 1);

			reverse(src, tempacs - 1);

		}

	}

	else {

		if (tempacs < tempdes)

		{

			desceding(src, 0, op[tempdesloc][1] - 1);

		}

		else {

			acsceding(src, 0, op[tempacsloc][1] - 1);

			reverse(src, tempdes - 1);

		}

	}



	//4.输出

	for (int i = 0; i < n; i++)

	{

		cout << src[i] << " ";

	}

}