There is a country with n citizens. The i-th of them initially has a_{i} money. The government strictly controls the wealth of its citizens. Whenever a citizen makes a purchase or earns some money, they must send a receipt to the social services mentioning the amount of money they currently have.

Sometimes the government makes payouts to the poor: all citizens who have strictly less money than x are paid accordingly so that after the payout they have exactly x money. In this case the citizens don't send a receipt.

You know the initial wealth of every citizen and the log of all events: receipts and payouts. Restore the amount of money each citizen has after all events.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^{5}) — the numer of citizens.

The next line contains n integers a_1, a_2, ..., a_n (0 ≤ a_{i} ≤ 10^{9}) — the initial balances of citizens.

The next line contains a single integer q (1 ≤ q ≤ 2 ⋅ 10^{5}) — the number of events.

Each of the next q lines contains a single event. The events are given in chronological order.

Each event is described as either 1 p x (1 ≤ p ≤ n, 0 ≤ x ≤ 10^{9}), or 2 x (0 ≤ x ≤ 10^{9}). In the first case we have a receipt that the balance of the p-th person becomes equal to x. In the second case we have a payoff with parameter x.

Output

Print n integers — the balances of all citizens after all events.

Examples

Input


4
1 2 3 4
3
2 3
1 2 2
2 1


Output


3 2 3 4 


Input


5
3 50 2 1 10
3
1 2 0
2 8
1 3 20


Output


8 8 20 8 10 

Note

In the first example the balances change as follows: 1 2 3 4 → 3 3 3 4 → 3 2 3 4 → 3 2 3 4

In the second example the balances change as follows: 3 50 2 1 10 → 3 0 2 1 10 → 8 8 8 8 10 → 8 8 20 8 10
from sys import stdin
from collections import deque
mod = 10**9 + 7
# def rl():
#     return [int(w) for w in stdin.readline().split()]
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt,factorial,gcd,log2,inf,ceil
# map(int,input().split())
# # l = list(map(int,input().split()))
# from itertools import permutations

# a = int(input())
# b = int(input())
# c = int(input())
# d = int(input())
# e = int(input())
# f = int(input())
# ans = 0
#
# for i in range(d+1):
#     c = e*(min(i,a)) + f*(min(d-i,c,b))
#     ans = max(c,ans)
#     print(c,i,a)
#
# print(ans)
# ans1 = 0
# ans2 = 0
# def bfs(n):
#     global ans1
#     boo1[n] = True
#     queue = [n]
#
#     while queue:
#
#         z = queue.pop(0)
#         if len(hash[z]) == 0:
#             ans1+=1
#         for i in hash[z]:
#
#             if not boo1[i]:
#                 queue.append(i)
#                 boo1[i] = True
#
# def bfs1(n):
#     global ans2
#     boo2[n] = True
#     queue = [n]
#
#     while queue:
#
#         z = queue.pop(0)
#         if len(hash1[z]) == 0:
#             ans2+=1
#         for i in hash1[z]:
#
#             if not boo2[i]:
#                 queue.append(i)
#                 boo2[i] = True
#
#
#
#
#
#
#
#
#
# hash = defaultdict(list)
# hash1 = defaultdict(list)
# n,m = map(int,input().split())
#
# for i in range(m):
#     a,b = map(int,input().split())
#     hash[a].append(b)
#     hash1[b].append(a)
#
#
#
# boo1 = defaultdict(bool)
# boo2 = defaultdict(bool)
#
# for i in range(1,n+1):
#     if boo1[i] == False:
#         bfs(i)
#     if boo2[i] == False:
#         bfs1(i)
#
#
# print(max(ans1,ans2))
#
#
#
#




n = int(input())

l = list(map(int,input().split()))

q = int(input())

query = []
for i in range(q):
    l1 = list(map(int,input().split()))
    if len(l1) == 2:
        a,b = l1
        query.append([a,b])

    else:
       a,b,c = l1
       query.append([a,b,c])

query.reverse()


maxi = 0
seti = set()
for i,j in enumerate(query):

    if len(query[i]) == 2:
        a,b = query[i]
        maxi = max(maxi,b)

    else:
        a,b,c = query[i]
        if b-1 not in seti:

         l[b-1] = max(maxi,c)
         seti.add(b-1)

for i in range(n):
  if i not in seti:
    l[i] = max(l[i],maxi)

print(*l)

