Each month Blake gets the report containing main economic indicators of the company "Blake Technologies". There are n commodities produced by the company. For each of them there is exactly one integer in the final report, that denotes corresponding revenue. Before the report gets to Blake, it passes through the hands of m managers. Each of them may reorder the elements in some order. Namely, the i-th manager either sorts first r_{i} numbers in non-descending or non-ascending order and then passes the report to the manager i + 1, or directly to Blake (if this manager has number i = m).

Employees of the "Blake Technologies" are preparing the report right now. You know the initial sequence a_{i} of length n and the description of each manager, that is value r_{i} and his favourite order. You are asked to speed up the process and determine how the final report will look like.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of commodities in the report and the number of managers, respectively.

The second line contains n integers a_{i} (|a_{i}| ≤ 10^9) — the initial report before it gets to the first manager.

Then follow m lines with the descriptions of the operations managers are going to perform. The i-th of these lines contains two integers t_{i} and r_{i} ($t_{i} \in \{1,2 \}$, 1 ≤ r_{i} ≤ n), meaning that the i-th manager sorts the first r_{i} numbers either in the non-descending (if t_{i} = 1) or non-ascending (if t_{i} = 2) order.


-----Output-----

Print n integers — the final report, which will be passed to Blake by manager number m.


-----Examples-----
Input
3 1
1 2 3
2 2

Output
2 1 3 
Input
4 2
1 2 4 3
2 3
1 2

Output
2 4 1 3 


-----Note-----

In the first sample, the initial report looked like: 1 2 3. After the first manager the first two numbers were transposed: 2 1 3. The report got to Blake in this form.

In the second sample the original report was like this: 1 2 4 3. After the first manager the report changed to: 4 2 1 3. After the second manager the report changed to: 2 4 1 3. This report was handed over to Blake.

Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
t = []
for i in range(m):
	(asc, r) = map(int, input().split())
	while t:
		if r >= t[-1][1]:
			t.pop()
		else:
			break
	t.append([asc, r])
t.append([0, 0])
x = 0
y = t[0][1] - 1
sor = sorted(a[:t[0][1]])
for i in range(1, len(t)):
	for j in range(t[i - 1][1], t[i][1], -1):
		if t[i - 1][0] == 1:
			a[j - 1] = sor[y]
			y -= 1
		else:
			a[j - 1] = sor[x]
			x += 1
print(' '.join(list((str(i) for i in a))))


import sys
from collections import deque
(n, m) = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
b = []
mx = 0
for i in range(m):
	t = tuple(map(int, sys.stdin.readline().split()))
	mx = max([mx, t[1]])
	b.append(t)
real = []
so_far = 0
for i in range(m - 1, -1, -1):
	if b[i][1] > so_far:
		real.append(b[i])
		so_far = b[i][1]
real.reverse()
answer = [0] * n
b = a[0:mx]
b.sort()
d = deque(b)
for i in range(mx, len(a)):
	answer[i] = a[i]
for i in range(len(real)):
	if i + 1 == len(real):
		for j in range(real[i][1]):
			if real[i][0] == 1:
				answer[j] = d.popleft()
			else:
				answer[j] = d.pop()
	else:
		for j in range(real[i][1] - 1, real[i + 1][1] - 1, -1):
			if real[i][0] == 1:
				answer[j] = d.pop()
			else:
				answer[j] = d.popleft()
print(' '.join(map(str, answer)))


(n, m) = [int(i) for i in input().split()]
rev = [int(i) for i in input().split()]
leng = len(rev)
result = list()
mark = list()
while m > 0:
	(t, r) = [int(i) for i in input().split()]
	while len(mark) > 0 and r >= mark[-1][1]:
		mark.pop()
	mark.append([t, r])
	m -= 1
mark.append([0, 0])
length = len(mark)
start = mark[0][1]
seq = mark[0][0]
(x, y) = (0, start - 1)
result = sorted(rev[:start])
for i in range(1, length):
	for j in range(mark[i - 1][1], mark[i][1], -1):
		if mark[i - 1][0] == 1:
			rev[j - 1] = result[y]
			y -= 1
		else:
			rev[j - 1] = result[x]
			x += 1
for i in range(0, leng):
	print(rev[i], sep=' ', end=' ')


read = lambda : map(int, input().split())
(n, m) = read()
a = list(read())
t = []
for i in range(m):
	(x, r) = read()
	while len(t) and r >= t[-1][1]:
		t.pop()
	t.append((x, r))
(x, r) = (0, t[0][1] - 1)
t.append((0, 0))
b = sorted(a[:r + 1])
for i in range(1, len(t)):
	for j in range(t[i - 1][1], t[i][1], -1):
		if t[i - 1][0] == 1:
			a[j - 1] = b[r]
			r -= 1
		else:
			a[j - 1] = b[x]
			x += 1
print(*a)


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
l = []
for i in range(m):
	(t, r) = [int(i) for i in input().split()]
	while len(l) > 0 and r >= l[-1][1]:
		l.pop()
	l.append([t, r])
(x, y) = (0, l[0][1] - 1)
l.append([0, 0])
b = sorted(a[:y + 1])
for i in range(1, len(l)):
	for j in range(l[i - 1][1], l[i][1], -1):
		if l[i - 1][0] == 1:
			a[j - 1] = b[y]
			y -= 1
		else:
			a[j - 1] = b[x]
			x += 1
print(' '.join((str(i) for i in a)))


from collections import deque
__author__ = 'aste'

def main():
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	q = [0] * m
	for i in range(0, m):
		(t, r) = map(int, input().split())
		q[i] = (r, t)
	max_range = [0] * m
	max_range[m - 1] = m - 1
	for i in range(m - 2, -1, -1):
		if q[i][0] > q[max_range[i + 1]][0]:
			max_range[i] = i
		else:
			max_range[i] = max_range[i + 1]
	max_range_global = q[max_range[0]][0]
	prefix = a[:max_range_global]
	suffix = a[max_range_global:]
	if q[max_range[0]][1] == 1:
		prefix.sort()
	else:
		prefix.sort(reverse=True)
	ops = []
	i = 0
	while i < m:
		ops.append(q[max_range[i]])
		i = max_range[i] + 1
	s = 0
	e = len(prefix)
	needs_reverse = 0
	res = deque()
	for i in range(1, len(ops)):
		diff = ops[i - 1][0] - ops[i][0]
		if needs_reverse:
			res.extendleft(prefix[s:s + diff])
			s += diff
		else:
			res.extendleft(reversed(prefix[e - diff:e]))
			e -= diff
		if ops[i][1] != ops[i - 1][1]:
			needs_reverse ^= 1
	if needs_reverse:
		res.extendleft(prefix[s:e])
	else:
		res.extendleft(reversed(prefix[s:e]))
	res = list(res) + suffix
	print(' '.join([str(x) for x in res]))
main()


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
manager = []
for i in range(m):
	t = [int(j) for j in input().split()]
	manager.append(t)
	j = len(manager) - 1
	while j > 0 and len(manager) > 1:
		if manager[j][1] > manager[j - 1][1]:
			del manager[j - 1]
			j -= 1
		else:
			break
temp = a[manager[0][1]:]
temp.reverse()
result = temp
del a[manager[0][1]:]
a.sort()
lm = len(manager)
(l, r) = (0, 0)
for i in range(lm):
	if i < lm - 1:
		if manager[i][0] == 1:
			for j in range(manager[i][1] - manager[i + 1][1]):
				result.append(a[-(1 + r)])
				r += 1
		elif manager[i][0] == 2:
			for j in range(manager[i][1] - manager[i + 1][1]):
				result.append(a[l])
				l += 1
	else:
		if r != 0:
			tem = a[l:-r]
		else:
			tem = a[l:]
		if manager[i][0] == 1:
			tem.reverse()
			result.extend(tem)
		elif manager[i][0] == 2:
			result.extend(tem)
result.reverse()
print(*result)


3

class StdReader:

	def read_int(self):
		return int(self.read_string())

	def read_ints(self, sep=None):
		return [int(i) for i in self.read_strings(sep)]

	def read_float(self):
		return float(self.read_string())

	def read_floats(self, sep=None):
		return [float(i) for i in self.read_strings(sep)]

	def read_string(self):
		return input()

	def read_strings(self, sep=None):
		return self.read_string().split(sep)
reader = StdReader()

def part_sort(a, i, j, reverse=False):
	a[i:j] = sorted(a[i:j], reverse=reverse)

def part_sorted(b, i, j, reverse=False):
	a = list(b)
	part_sort(a, i, j, reverse)
	return a

def main():
	(n, m) = reader.read_ints()
	a = reader.read_ints()
	ops = []
	for i in range(m):
		(t, r) = reader.read_ints()
		op = (t, r)
		while ops and op[1] >= ops[-1][1]:
			ops.pop()
		ops.append(op)
	max_r = ops[0][1]
	b = sorted(a[:max_r])
	bl = 0
	br = max_r - 1
	for i in range(len(ops)):
		(t, r) = ops[i]
		r1 = 0
		if i < len(ops) - 1:
			(t1, r1) = ops[i + 1]
		k = r - r1
		if t == 1:
			for p in range(k):
				a[r - 1 - p] = b[br]
				br -= 1
		else:
			for p in range(k):
				a[r - 1 - p] = b[bl]
				bl += 1
	for ai in a:
		print(ai, end=' ')

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
deq = []
for i in range(0, m):
	(t, r) = map(int, input().split())
	while deq and deq[-1][1] < r:
		deq.pop(-1)
	deq.append((t, r))
b = sorted(a[0:deq[0][1]])
seq = []
for (t, r) in deq:
	if seq:
		it = (t,) + ((seq[-1][2] - r, seq[-1][2]) if seq[-1][0] == 2 else (seq[-1][1], seq[-1][1] + r))
		seq[-1] = (seq[-1][0],) + ((seq[-1][1], seq[-1][2] - r) if seq[-1][0] == 2 else (seq[-1][1] + r, seq[-1][2]))
		seq.append(it)
	else:
		seq.append((t, 0, r))
c = []
for (t, l, r) in reversed(seq):
	c.extend((lambda x: x if t == 1 else reversed(x))(b[l:r]))
c.extend(a[deq[0][1]:])
print(' '.join(map(str, c)))


(n, m) = [int(i) for i in input().split()]
adata = [int(i) for i in input().split()]
t = [None] * m
r = [None] * m
for i in range(m):
	(t[i], r[i]) = [int(j) for j in input().split()]
Sortlist = []
Sortcount = 0
M = 0
for i in range(m - 1, -1, -1):
	if r[i] > M:
		Sortlist.append([r[i], t[i]])
		Sortcount += 1
		M = r[i]
S = sorted(adata[0:Sortlist[-1][0]])
L = 0
R = M - 1
for i in range(M - 1, -1, -1):
	if Sortcount > 0:
		if i < Sortlist[Sortcount - 1][0]:
			Reverse = Sortlist[Sortcount - 1][1]
			Sortcount -= 1
	if Reverse == 1:
		adata[i] = S[R]
		R -= 1
	else:
		adata[i] = S[L]
		L += 1
for i in adata[0:-1]:
	print(str(i) + ' ', end='')
print(adata[-1])


from sys import setrecursionlimit
setrecursionlimit(200000)

class data:

	def __init__(self, a):
		self.data = a

	def qsort(self, l, r, reverse):
		if l >= r:
			return None
		ind = l
		i = l
		j = r
		key = self.data[l]
		while i < j:
			if reverse == 1:
				while (self.data[j] >= key) & (j >= l):
					j -= 1
				while (self.data[i] < key) & (i <= r):
					i += 1
					ind = i - 1
				if i < j:
					ind += 1
					t = self.data[i]
					self.data[i] = self.data[j]
					self.data[j] = t
			else:
				while (self.data[j] <= key) & (j >= l):
					j -= 1
					ind = j + 1
				while (self.data[i] > key) & (i <= r):
					i += 1
				if i < j:
					ind -= 1
					t = self.data[i]
					self.data[i] = self.data[j]
					self.data[j] = t
		self.qsort(l, ind, reverse)
		self.qsort(ind + 1, r, reverse)
(n, m) = [int(i) for i in input().split()]
a = data([int(i) for i in input().split()])
t = [None] * m
r = [None] * m
for i in range(m):
	(t[i], r[i]) = [int(j) for j in input().split()]
Sortlist = []
Sortcount = 0
M = 0
for i in range(m - 1, -1, -1):
	if r[i] > M:
		Sortlist.append([r[i], t[i]])
		Sortcount += 1
		M = r[i]
S = sorted(a.data[0:Sortlist[-1][0]])
L = 0
R = M - 1
for i in range(M - 1, -1, -1):
	if Sortcount > 0:
		if i < Sortlist[Sortcount - 1][0]:
			Reverse = Sortlist[Sortcount - 1][1]
			Sortcount -= 1
	if Reverse == 1:
		a.data[i] = S[R]
		R -= 1
	else:
		a.data[i] = S[L]
		L += 1
for i in a.data[0:-1]:
	print(str(i) + ' ', end='')
print(a.data[-1])


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
t = []
for i in range(m):
	(s, r) = map(int, input().split())
	while t and r >= t[-1][1]:
		t.pop()
	t.append([s, r])
t.append([0, 0])
(x, y) = (0, t[0][1] - 1)
res = sorted(a[:t[0][1]])
for i in range(1, len(t)):
	for j in range(t[i - 1][1], t[i][1], -1):
		if t[i - 1][0] == 1:
			a[j - 1] = res[y]
			y -= 1
		else:
			a[j - 1] = res[x]
			x += 1
print(*a)


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
b = list(map(int, stdin.readline().split()))
a = []
for i in range(m):
	a.append(tuple(map(int, stdin.readline().split())))
a = a[::-1]
r = [a[0]]
now = a[0]
f = 0
for i in range(m):
	if a[i][1] > now[1]:
		if now[0] == a[i][0] and f:
			r.remove(now)
		r.append(a[i])
		now = a[i]
		f = 1
maxi = r[-1]
vos = sorted(b[0:maxi[1]])
ub = vos[::-1]
u = maxi[1] - 1
v = maxi[1] - 1
l = len(r)
r = [(0, 0)] + r
res = [0] * n
pr = [0] * n
for i in range(len(r) - 1):
	for j in range(r[i][1], r[i + 1][1]):
		pr[j] = r[i + 1][0]
for i in range(n - 1, -1, -1):
	if pr[i] == 1:
		res[i] = vos[v]
		v -= 1
	elif pr[i] == 2:
		res[i] = ub[u]
		u -= 1
	else:
		res[i] = b[i]
res = list(map(str, res))
stdout.write(' '.join(res))


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(1):
	(n, m) = lst()
	a = lst()
	l = [lst() for _ in range(m)]
	suf = [0] * (1 + m)
	suf[m - 1] = l[m - 1][1]
	for i in range(m - 2, -1, -1):
		suf[i] = max(suf[i + 1], l[i][1])
	chng = []
	for i in range(m):
		if suf[i] == l[i][1]:
			if not chng or l[i][0] != chng[-1][0]:
				chng += [[l[i][0], l[i][1]]]
	if chng[0][0] == 1:
		pos = chng[0][1] - 1
		ans = sorted(a[:pos + 1]) + a[pos + 1:]
		next = 1
	else:
		pos = chng[0][1] - 1
		ans = sorted(a[:pos + 1], reverse=True) + a[pos + 1:]
		next = 1
	ln = len(chng)
	c = 0
	if ln >= 2:
		c = chng[1][1] - 1
	(start, end) = (0, c)
	a = ans.copy()
	for i in range(1, ln):
		if next & 1:
			diff = chng[i][1] - (0 if i + 1 >= ln else chng[i + 1][1])
			while diff > 0:
				ans[c] = a[start]
				c -= 1
				start += 1
				diff -= 1
		else:
			diff = chng[i][1] - (0 if i + 1 >= ln else chng[i + 1][1])
			while diff > 0:
				ans[c] = a[end]
				c -= 1
				end -= 1
				diff -= 1
		next += 1
	print(*ans)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
k = []
for t in range(m):
	(x, y) = map(int, input().split())
	while len(k) > 0 and k[-1][1] < y:
		k.pop()
	k.append([x, y])
a = 0
b = k[0][1] - 1
k.append([0, 0])
sr = sorted(l[:b + 1])
for i in range(1, len(k)):
	for j in range(k[i - 1][1], k[i][1], -1):
		if k[i - 1][0] == 1:
			l[j - 1] = sr[b]
			b -= 1
		else:
			l[j - 1] = sr[a]
			a += 1
print(*l)


from sys import stdin
(n, m) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
lst = list()
for i in range(m):
	(t, r) = map(int, stdin.readline().split())
	while lst and lst[-1][1] < r:
		x = lst.pop()
	if t == 2:
		t = -1
	lst.append((t, r))
lst.append((0, 0))
b = sorted(a[:lst[0][1]])
l = 0
r = len(b) - 1
for i in range(len(lst) - 1):
	for j in range(lst[i][1] - 1, lst[i + 1][1] - 1, -1):
		if lst[i][0] == -1:
			a[j] = b[l]
			l += 1
		else:
			a[j] = b[r]
			r -= 1
print(' '.join([str(x) for x in a]))


__author__ = 'Utena'
import operator
(n, m) = map(int, input().split())
s = list(map(int, input().split()))
r0 = [[0, 10000000000]]
x0 = [0]
for i in range(m):
	(t, r) = map(int, input().split())
	while r >= r0[-1][1]:
		r0 = r0[:-1]
		x0 = x0[:-1]
	r0.append([t, r])
	x0.append(i)
Q = sorted(s[:r0[1][1]])
r0.append([0, 0])
x = 0
j = 2
y = r0[1][1] - 1
i = r0[1][1] - 1
while True:
	while i >= r0[j][1]:
		if r0[j - 1][0] == 2:
			temp = Q[x]
			x += 1
		else:
			temp = Q[y]
			y -= 1
		s[i] = temp
		i -= 1
		if i < 0:
			break
	j += 1
	if y < x:
		break
print(' '.join(map(str, s)))


(n, m) = map(int, input().split())
A = list(map(int, input().split()))
M = [list(map(int, input().split())) for _ in range(m)]
j = m - 1
x = 2
h = -1
B = [-1 for _ in range(n + 1)]
while h < n and j >= 0:
	h = M[j][1]
	if h >= x:
		B[h] = j
		x = h + 1
	j -= 1
O = [0 for _ in range(n)]
for i in range(n - 1, x - 2, -1):
	O[i] = A[i]
	del A[i]
n2 = len(A)
R = A[:]
R.sort()
d = 0
f = n2 - 1
c = 0
for i in range(n2 - 1, -1, -1):
	j = B[i + 1]
	if j >= 0:
		c = M[j][0]
	if c == 1:
		O[i] = R[f]
		f -= 1
	else:
		O[i] = R[d]
		d += 1
for i in range(n):
	print(O[i], end=' ')


s = input()
num = [int(x) for x in s.split()]
(n, m) = (num[0], num[1])
s = input()
a = [int(x) for x in s.split()]
t1 = [0 for x in range(m)]
r1 = [0 for x in range(m)]
for i in range(m):
	s = input()
	num = [int(x) for x in s.split()]
	(t1[i], r1[i]) = (num[0], num[1])
	r1[i] = r1[i] - 1
	if t1[i] is 2:
		t1[i] = -1
t = []
r = []
for i in range(m):
	while len(r) != 0 and r[-1] <= r1[i]:
		t.pop()
		r.pop()
	t.append(t1[i])
	r.append(r1[i])
m = len(t)
b = [0 for x in range(n)]
last = 0
for i in range(m - 1, -1, -1):
	if r[i] > last:
		last = r[i]
		b[r[i]] = t[i]
r = []
r.extend(a)
for i in range(n - 1, -1, -1):
	if b[i] is 1:
		c = sorted(a[:i + 1])
		c.extend(a[i + 1:])
		typ = b[i]
		r = []
		r.extend(c)
		le = 0
		ri = i - 1
		tp = typ
		for j in range(i - 1, -1, -1):
			if b[j] is not 0:
				tp = b[j]
			if tp == typ:
				r[j] = c[ri]
				ri = ri - 1
			else:
				r[j] = c[le]
				le = le + 1
		break
	elif b[i] is -1:
		c = sorted(a[:i + 1])
		c.reverse()
		c.extend(a[i + 1:])
		typ = b[i]
		r = []
		r.extend(c)
		le = 0
		ri = i - 1
		tp = typ
		for j in range(i - 1, -1, -1):
			if b[j] is not 0:
				tp = b[j]
			if tp == typ:
				r[j] = c[ri]
				ri = ri - 1
			else:
				r[j] = c[le]
				le = le + 1
		break
for j in range(len(r)):
	print(r[j], end=' ')
print()


(n, m) = [int(i) for i in input().split()]
nl = [int(i) for i in input().split()]
ml = []
for i in range(m):
	(t, r) = [int(k) for k in input().split()]
	ml.append((t, r))
mll = [(0, 0)]
for i in range(m - 1, -1, -1):
	if i == m - 1:
		mll.append(ml[i])
	elif i != m - 1 and ml[i][1] > mll[-1][1]:
		mll.append(ml[i])
temp = sorted(nl[:mll[len(mll) - 1][1]])
(x, y) = (0, len(temp) - 1)
for i in range(len(mll) - 1, 0, -1):
	(t, r) = mll[i]
	for j in range(r - 1, mll[i - 1][1] - 1, -1):
		if t == 1:
			nl[j] = temp[y]
			y -= 1
		elif t == 2:
			nl[j] = temp[x]
			x += 1
for i in range(n):
	nl[i] = str(nl[i])
print(' '.join(nl))


def compress(ops):
	cops = []
	for (r, dir) in ops:
		while cops and cops[-1][0] <= r:
			cops.pop()
		if not cops or cops[-1][1] != dir:
			cops.append((r, dir))
	return cops

def transform(lst, ops):
	(mr, mdir) = ops[0]
	sections = [list(range(mr, len(lst)))]
	ost = 0
	oen = mr
	(pr, pdir) = ops[0]
	for (r, dir) in ops[1:]:
		k = pr - r
		if pdir:
			sections.append(reversed(list(range(ost, ost + k))))
			ost += k
		else:
			sections.append(list(range(oen - k, oen)))
			oen -= k
		(pr, pdir) = (r, dir)
	if pdir:
		sections.append(reversed(list(range(ost, oen))))
	else:
		sections.append(list(range(ost, oen)))
	olst = lst[:mr]
	olst.sort()
	olst.extend(lst[mr:])
	return [olst[i] for sec in reversed(sections) for i in sec]

def parse_op():
	(d, r) = input().split()
	return (int(r), d == '2')

def parse_input():
	(n, m) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	assert len(lst) == n
	ops = [parse_op() for _ in range(m)]
	return (lst, ops)

def __starting_point():
	(lst, ops) = parse_input()
	cops = compress(ops)
	tlst = transform(lst, cops)
	print(' '.join(map(str, tlst)))
__starting_point()


def main():
	from collections import deque
	(n, m) = map(int, input().split())
	aa = list(map(int, input().split()))
	l = list((tuple(map(int, input().split())) for _ in range(m)))
	(tmp, r0, t0) = ([(0, 0)], 0, 0)
	for (t, r) in reversed(l):
		if r0 < r:
			r0 = r
			if t0 != t:
				t0 = t
				tmp.append((t, r))
			else:
				tmp[-1] = (t, r)
	(t0, r0) = tmp.pop()
	q = deque(sorted(aa[:r0]))
	aa = aa[r0:]
	aa.reverse()
	ff = (None, q.pop, q.popleft)
	for (t, r) in reversed(tmp):
		f = ff[t0]
		for i in range(r0 - r):
			aa.append(f())
		(t0, r0) = (t, r)
	print(' '.join(map(str, reversed(aa))))
main()


(n, m) = input().split()
n = int(n)
m = int(m)
ma = []
p = 0
s = input().split()
for i in range(n):
	s[i] = int(s[i])
for i in range(m):
	t = [int(j) for j in input().split()]
	ma.append(t)
	j = len(ma) - 1
	while j > 0 and len(ma) > 1:
		if ma[j][1] > ma[j - 1][1]:
			del ma[j - 1]
			j -= 1
		else:
			break
temp = s[ma[0][1]:]
temp.reverse()
result = temp
del s[ma[0][1]:]
s.sort()
lm = len(ma)
(l, r) = (0, 0)
for i in range(lm):
	if i < lm - 1:
		if ma[i][0] == 1:
			for j in range(ma[i][1] - ma[i + 1][1]):
				result.append(s[-(1 + r)])
				r += 1
		elif ma[i][0] == 2:
			for j in range(ma[i][1] - ma[i + 1][1]):
				result.append(s[l])
				l += 1
	else:
		if r != 0:
			tem = s[l:-r]
		else:
			tem = s[l:]
		if ma[i][0] == 1:
			tem.reverse()
			result.extend(tem)
		elif ma[i][0] == 2:
			result.extend(tem)
result.reverse()
print(' '.join((str(i) for i in result)))


(n, m) = map(int, input().split())
lis = list(map(int, input().split()))
q = []
for i in range(m):
	(a, b) = map(int, input().split())
	while len(q) > 0 and b >= q[-1][1]:
		q.pop()
	q.append([a, b])
(a, b) = (0, q[0][1] - 1)
q.append([0, 0])
aa = sorted(lis[:b + 1])
for i in range(1, len(q)):
	for j in range(q[i - 1][1], q[i][1], -1):
		if q[i - 1][0] == 1:
			lis[j - 1] = aa[b]
			b -= 1
		else:
			lis[j - 1] = aa[a]
			a += 1
print(*lis)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
managers = []
for i in range(m):
	managers += [list(map(int, input().split()))]
effective = []
mx = 0
for i in range(m - 1, -1, -1):
	if managers[i][1] > mx:
		effective += [managers[i]]
		mx = managers[i][1]
A = sorted(a[:effective[-1][1]])
x = 0
y = effective[-1][1] - 1
effective = [[0, 0]] + effective
for i in range(len(effective) - 1, -1, -1):
	for j in range(effective[i][1], effective[i - 1][1], -1):
		if x > y:
			break
		if effective[i][0] == 1:
			a[j - 1] = A[y]
			y -= 1
		elif effective[i][0] == 2:
			a[j - 1] = A[x]
			x += 1
print(' '.join(list(map(str, a))))


(a, b) = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
s = []
for p in range(b):
	s += [[int(i) for i in input().split()]]
S = []
k = 0
for p in range(b - 1, -1, -1):
	if s[p][1] > k:
		S += [s[p]]
		k = s[p][1]
Q1 = sorted(q[:S[-1][1]])
(x, y) = (0, S[-1][1] - 1)
S = [[0, 0]] + S
l = 1
for j in range(S[-1][1] - 1, -1, -1):
	if x > y:
		break
	if j < S[-l][1]:
		k = S[-l][0]
		l += 1
	if k == 1:
		q[j] = Q1[y]
		y -= 1
	if k == 2:
		q[j] = Q1[x]
		x += 1
print(' '.join(list(map(str, q))))


from collections import *
from sys import stdin

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return list(stdin.readline()[:-1])
(n, m) = arr_inp(1)
(a, mem, ans, en) = (arr_inp(1), defaultdict(lambda : [0, 0]), deque(), n - 1)
for i in range(m):
	(t, r) = arr_inp(1)
	mem[r] = [t, i]
for i in range(n - 1, -1, -1):
	if not mem[i + 1][0]:
		ans.appendleft(a[i])
		en -= 1
	else:
		break
(tem, last, time) = (deque(sorted(a[:en + 1])), 0, -1)
for j in range(en, -1, -1):
	if mem[j + 1][0] == 1 and mem[j + 1][1] > time:
		ans.appendleft(tem.pop())
		(last, time) = (1, mem[j + 1][1])
	elif mem[j + 1][0] == 2 and mem[j + 1][1] > time:
		ans.appendleft(tem.popleft())
		(last, time) = (2, mem[j + 1][1])
	elif last == 1:
		ans.appendleft(tem.pop())
	else:
		ans.appendleft(tem.popleft())
print(*ans)


def main():
	(n, m) = input().strip().split()
	(n, m) = (int(n), int(m))
	initial = list(map(int, input().strip().split()))
	max_r = 0
	reports = [None] * n
	for i in range(m):
		(order, last_rep) = input().strip().split()
		last_rep = int(last_rep)
		max_r = max(max_r, last_rep)
		reports[last_rep - 1] = (i, order)
	prev = None
	for i in reversed(range(n)):
		if reports[i] is None and prev is None:
			continue
		elif reports[i] is not None and prev is None:
			prev = reports[i]
			continue
		if reports[i] is None:
			reports[i] = prev
			continue
		if reports[i][0] < prev[0]:
			reports[i] = prev
		else:
			prev = reports[i]
	reports = list(map(lambda pair: pair[1] if pair is not None else None, reports))
	result = []
	for i in reversed(range(n)):
		if i == max_r - 1:
			break
		result.append(initial[i])
	begin = 0
	end = max_r - 1
	arr = initial[begin:max_r]
	arr.sort()
	for i in reversed(range(max_r)):
		if reports[i] == '2':
			target = begin
			begin += 1
		elif reports[i] == '1':
			target = end
			end -= 1
		result.append(arr[target])
	result.reverse()
	print(*result)
main()


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, m) = value()
a = array()
status = defaultdict(int)
till = -1
given = []
for i in range(m):
	(s, r) = value()
	given.append((s, r))
for (s, r) in given[::-1]:
	if r - 1 > till:
		till = r - 1
		if s == 2:
			s = -1
		status[r - 1] = s * -1
ans = [-1] * n
have = a[:till + 1]
for i in range(till + 1, n):
	ans[i] = a[i]
have.sort()
inc = 1
low = 0
high = till
for i in range(till, -1, -1):
	if status[i] != 0:
		inc = status[i]
		if status[i] == 1:
			ind = low
		else:
			ind = high
	if inc == 1:
		ans[i] = have[low]
		low += 1
	else:
		ans[i] = have[high]
		high -= 1
print(*ans)


import sys
(n, m) = [int(x) for x in input().split()]
notes = [int(x) for x in input().split()]
managers = []
for line in sys.stdin:
	managers.append(tuple((int(x) for x in line.split())))
bearing_managers = []
(M, T) = (0, 0)
for (t, r) in reversed(managers):
	if r > M:
		if t == T:
			bearing_managers[-1] = (t, r)
		else:
			T = t
			bearing_managers.append((t, r))
		M = r
bearing_managers.reverse()
(t, r) = bearing_managers[0]
bearing_managers.append((2 if bearing_managers[-1][0] == 1 else 1, 0))
(L, R) = (0, r - 1)
sorted_part = list(sorted(notes[:r]))
for (t1, r1) in bearing_managers:
	if t1 == 2:
		for i in range(r - 1, r1 - 1, -1):
			notes[i] = sorted_part[R]
			R -= 1
	else:
		for i in range(r - 1, r1 - 1, -1):
			notes[i] = sorted_part[L]
			L += 1
	r = r1
for x in notes:
	sys.stdout.write(str(x) + ' ')


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
from collections import deque
managers = deque()
for i in range(m):
	(t, r) = [int(j) for j in input().split()]
	while len(managers) > 0 and managers[-1][1] <= r:
		managers.pop()
	if len(managers) > 0 and managers[-1][0] != t or len(managers) == 0:
		managers.append([t, r])
l = len(managers)
managers.append([1, 0])
(t1, r1) = managers.popleft()
b = a[0:r1]
times = 0
first = 0
last = r1 - 1
now = r1 - 1
if t1 == 1:
	b = sorted(b)
else:
	b = sorted(b, reverse=True)
for i in range(l):
	(t2, r2) = managers.popleft()
	if times % 2 == 0:
		for j in range(r1 - r2):
			a[now] = b[last]
			last -= 1
			now -= 1
	else:
		for j in range(r1 - r2):
			a[now] = b[first]
			first += 1
			now -= 1
	(t1, r1) = (t2, r2)
	times += 1
print(' '.join([str(i) for i in a]))


import sys
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
s = []
for i in range(m):
	(t, r) = map(int, input().split())
	t -= 1
	r -= 1
	while s and s[-1][1] <= r:
		s.pop()
	s.append([t, r])
s.append([-1, -1])
sorted_slice = sorted(a[:s[0][1] + 1])
l = 0
r = s[0][1]
for i in range(len(s) - 1):
	if s[i][0]:
		for j in range(s[i][1], s[i + 1][1], -1):
			a[j] = sorted_slice[l]
			l += 1
	else:
		for j in range(s[i][1], s[i + 1][1], -1):
			a[j] = sorted_slice[r]
			r -= 1
print(*a)


(n, m) = [int(i) for i in input().split()]
_report = [int(i) for i in input().split()]
working = []
for i in range(m):
	(x, y) = map(int, input().split())
	while len(working) != 0 and y >= working[-1][1]:
		working.pop()
	working.append([x, y])
P = working[0][1]
sample = _report[:P]
sample.sort()
x = 0
y = P - 1
working.append([0, 0])
for i in range(len(working) - 1):
	for j in range(working[i][1], working[i + 1][1], -1):
		if working[i][0] == 1:
			_report[j - 1] = sample[y]
			y -= 1
		if working[i][0] == 2:
			_report[j - 1] = sample[x]
			x += 1
print(' '.join(map(str, _report)))


(n, m) = [int(i) for i in input().split()]
a = list(map(int, input().split()))
b = []
for i in range(m):
	(t, r) = [int(x) for x in input().split()]
	while len(b) > 0 and r >= b[-1][1]:
		b.pop()
	b.append([t, r])
(t, r) = (0, b[0][1])
b.append([0, 0])
f = sorted(a[:r])
for i in range(1, len(b)):
	for y in range(b[i - 1][1], b[i][1], -1):
		if b[i - 1][0] == 1:
			a[y - 1] = f[r - 1]
			r -= 1
		else:
			a[y - 1] = f[t]
			t += 1
print(' '.join(list((str(i) for i in a))))


str1 = input().split()
n = int(str1[0])
m = int(str1[1])
a = list(map(int, input().split()))
oper = []
for i in range(m):
	tmp = list(map(int, input().split()))
	while len(oper) > 0 and tmp[1] > oper[-1][1]:
		oper.pop()
	oper.append([tmp[0], tmp[1]])
b = []
for i in range(oper[0][1], n):
	b.append(a.pop())
a = sorted(a)
order = oper[0][0]
front = 0
back = len(a) - 1
for i in range(1, len(oper)):
	for j in range(oper[i][1], oper[i - 1][1]):
		if order == 1:
			b.append(a[back])
			back -= 1
		else:
			b.append(a[front])
			front += 1
	order = oper[i][0]
for i in range(back - front + 1):
	if order == 1:
		b.append(a[back])
		back -= 1
	else:
		b.append(a[front])
		front += 1
for i in range(n - 1, -1, -1):
	print(b[i], end=' ')


[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
t = m * [0]
r = m * [0]
for k in range(0, m):
	[t[k], r[k]] = [int(i) for i in input().split()]
tstack = []
rstack = []
mm = -1
lastt = -1
tstack.append(t[0])
rstack.append(r[0])
top = 0
for i in range(1, m):
	while top > -1:
		if r[i] >= rstack[top]:
			rstack.pop()
			tstack.pop()
			top = top - 1
		else:
			break
	if top == -1:
		rstack.append(r[i])
		tstack.append(t[i])
		top = top + 1
	elif tstack[top] != t[i]:
		rstack.append(r[i])
		tstack.append(t[i])
		top = top + 1
r0 = rstack[0]
sorteda = sorted(a[:r0])
begin = 0
end = len(sorteda) - 1
for mindex in range(0, len(tstack) - 1):
	rthis = rstack[mindex]
	rnext = rstack[mindex + 1]
	if tstack[mindex] == 1:
		for i in range(rthis - 1, rnext - 1, -1):
			a[i] = sorteda[end]
			end = end - 1
	else:
		for i in range(rthis - 1, rnext - 1, -1):
			a[i] = sorteda[begin]
			begin = begin + 1
if tstack[-1] == 1:
	for i in range(0, rstack[-1]):
		a[i] = sorteda[i + begin]
else:
	for i in range(0, rstack[-1]):
		a[i] = sorteda[end - i]
print(*a, sep=' ')


from collections import deque
(n, k) = map(int, input().split())
arr = [int(x) for x in input().split()]
query = []
for i in range(k):
	(a, b) = map(int, input().split())
	if query:
		if b >= query[-1][1]:
			while query and b >= query[-1][1]:
				query.pop()
			query.append([a, b])
		else:
			query.append([a, b])
	else:
		query.append([a, b])
deq = deque(sorted(arr[:query[0][1]]))
for i in range(len(query) - 1):
	(ty, b) = (query[i][0], query[i][1])
	nex = query[i + 1][1]
	if ty == 1:
		for idx in range(b - 1, nex - 1, -1):
			arr[idx] = deq[-1]
			deq.pop()
	else:
		for idx in range(b - 1, nex - 1, -1):
			arr[idx] = deq[0]
			deq.popleft()
for i in range(query[-1][1] - 1, -1, -1):
	if query[-1][0] == 1:
		arr[i] = deq[-1]
		deq.pop()
	else:
		arr[i] = deq[0]
		deq.popleft()
print(*arr)


(a, b) = (int(i) for i in input().split())
f = list(map(int, input().split()))
d = []
for i in range(b):
	(c, e) = (int(t) for t in input().split())
	while len(d) > 0 and e > d[-1][1]:
		d.pop()
	d.append([c, e])
(c, e) = (0, d[0][1])
d.append([0, 0])
g = sorted(f[:e])
for i in range(1, len(d)):
	for y in range(d[i - 1][1], d[i][1], -1):
		if d[i - 1][0] == 1:
			f[y - 1] = g[e - 1]
			e -= 1
		else:
			f[y - 1] = g[c]
			c += 1
print(' '.join(list((str(i) for i in f))))


import sys, os.path
from collections import *
from copy import *
import math
mod = 10 ** 9 + 7
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
t = []
b = []
for i in range(m):
	(x, r) = map(int, input().split())
	while len(t) > 0 and r >= t[-1][1]:
		t.pop()
	t.append([x, r])
x = 0
y = t[0][1] - 1
t.append([0, 0])
b = sorted(a[:y + 1])
for i in range(1, len(t)):
	for j in range(t[i - 1][1], t[i][1], -1):
		if t[i - 1][0] == 1:
			a[j - 1] = b[y]
			y -= 1
		else:
			a[j - 1] = b[x]
			x += 1
print(*a)


(n, m) = input().split()
n = int(n)
m = int(m)
revenue = [int(i) for i in input().split()]
manager = [0 for i in range(n)]
operate = [0 for i in range(n)]
ans = [0 for i in range(n)]
for i in range(m):
	operations = [int(j) for j in input().split()]
	manager[operations[1] - 1] = i
	operate[operations[1] - 1] = operations[0]
for i in range(n - 1, -1, -1):
	if operate[i] == 0:
		ans[i] = revenue[i]
	else:
		max = i
		break
b = revenue[0:max + 1]
b.sort()
managernow = manager[max]
operatenow = operate[max]
s1 = max
s2 = 0
for i in range(max, -1, -1):
	if manager[i] > managernow and operatenow != 0:
		managernow = manager[i]
		operatenow = operate[i]
	if operatenow == 1:
		ans[i] = b[s1]
		s1 -= 1
	else:
		ans[i] = b[s2]
		s2 += 1
for i in range(n - 1):
	print(ans[i], end=' ')
print(ans[-1])