n, m = map(int, input().split())
assert 1 <= n <= 2 * 10 ** 5
assert 1 <= m <= 2 * 10 ** 5
a = list(map(int, input().split()))
b = list(map(int, input().split()))
assert 1 <= min(a)
assert max(a) <= 10 ** 9
assert 1 <= min(b)
assert max(b) <= 10 ** 9
for _ in range(m):
  t, c = map(int, input().split())
  assert t in [0, 1]
  assert 1 <= c <= 10 ** 9