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 \le n \le 2 \cdot 10^{5}$) — the numer of citizens.

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

The next line contains a single integer $q$ ($1 \le q \le 2 \cdot 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 \le p \le n$, $0 \le x \le 10^{9}$), or 2 x ($0 \le x \le 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 $\rightarrow$ 3 3 3 4 $\rightarrow$ 3 2 3 4 $\rightarrow$ 3 2 3 4

In the second example the balances change as follows: 3 50 2 1 10 $\rightarrow$ 3 0 2 1 10 $\rightarrow$ 8 8 8 8 10 $\rightarrow$ 8 8 20 8 10

Difficulty: competition

Starter code:

Solutions:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
changes=[0]*q
for i in range(q):
    changes[-i-1]=tuple(map(int,input().split()))
final=[-1]*n
curr=0
for guy in changes:
    if guy[0]==1:
        if final[guy[1]-1]==-1:
            final[guy[1]-1]=max(guy[2],curr)
    else:
        curr=max(curr,guy[1])
for i in range(n):
    if final[i]==-1:
        final[i]=max(curr,a[i])
final=[str(guy) for guy in final]
print(" ".join(final))

import sys
input = sys.stdin.readline

from bisect import bisect_left as bl

N = int(input())
A = [int(a) for a in input().split()]
Q = int(input())
L = [-1] * N

X = []
Y = []

for i in range(Q):
    t = [int(a) for a in input().split()]
    if t[0] == 1:
        p, x = t[1]-1, t[2]
        A[p] = x
        L[p] = i
    else:
        x = t[1]
        while len(Y) and Y[-1] <= x:
            X.pop()
            Y.pop()
        X.append(i)
        Y.append(x)
    
for i in range(N):
    j = bl(X, L[i])
    if j < len(X):
        A[i] = max(A[i], Y[j])

print(*A)



import sys
input = sys.stdin.readline

n = int(input())
l = list(map(int,input().split()))
lUpd = [0]*n
q = int(input())

payoff = [-1]*q
for query in range(q):
    qnext = list(map(int,input().split()))
    if qnext[0] == 1:
        p = qnext[1] - 1
        x = qnext[2]
        l[p] = x
        lUpd[p] = query
    else:
        x = qnext[1]
        payoff[query] = x

maxPayoff = [-1]*q
best = -1
for i in range(q-1,-1,-1):
    best = max(best,payoff[i])
    maxPayoff[i] = best

out = [max(l[p], maxPayoff[lUpd[p]]) for p in range(n)]
print(' '.join(map(str,out)))
        


import sys
input = sys.stdin.readline

n = int(input())
l = list(map(int,input().split()))
lUpd = [0]*n
q = int(input())

payoff = [-1]*q
for query in range(q):
    qnext = list(map(int,input().split()))
    if qnext[0] == 1:
        p = qnext[1] - 1
        x = qnext[2]
        l[p] = x
        lUpd[p] = query
    else:
        x = qnext[1]
        payoff[query] = x

maxPayoff = [-1]*q
best = -1
for i in range(q-1,-1,-1):
    best = max(best,payoff[i])
    maxPayoff[i] = best

out = [max(l[p], maxPayoff[lUpd[p]]) for p in range(n)]
print(' '.join(map(str,out)))
        


n = int(input())
a = list(map(int, input().split()))
q = int(input())

last_set = [0] * n
alles = [0]

for i in range(q):
    r = list(map(int, input().split()))
    if len(r) == 2:
        alles.append(r[1])
    else:
        last_set[r[1]-1] = len(alles)
        a[r[1]-1] = r[2]
        
maxis = alles
i = len(maxis) -1 
prev_max = 0
while i >= 0:
    prev_max = max(prev_max, alles[i])
    maxis[i] = prev_max
    i -= 1
    
for i in range(n):
    if last_set[i] < len(maxis):
        a[i] = max(a[i], maxis[last_set[i]])
    
print(" ".join(map(str, a)))


n=int(input())
a=list(map(int,input().split()))
q=int(input())
r1=[-1]*q
r2=[-1]*q
for i in range(q):
    ne=list(map(int,input().split()))
    if ne[0]==1:
        p=ne[1]-1
        t=ne[2]
        r1[i]=[p,t]
    else:
        r2[i]=ne[1]

b=-1
for i in range(q-1,-1,-1):
    b=max(b,r2[i])
    r2[i]=b

m=r2[0]
for i in range(n):
    a[i]=max(a[i],m)
    
for i in range(q):
    if r1[i]==-1:
        pass
    else:
        a[r1[i][0]]=max(r1[i][1],r2[i])
        
print(*a)

n = int(input())
array = list(map(int, input().split()))
q = int(input())
d = {i:0 for i in range(n)}
stack = []
for i in range(q):
    req = list(map(int, input().split()))
    if req[0] == 2:
        stack.append((req[1], i))
    else:
        p = req[1]-1
        d[p] = i
        array[p] = req[2]
ans_i = [-1]*q
j = len(stack)-1
max_of_stack = -1
for i in range(q-1, -1, -1):
    if j > -1 and stack[j][1] >= i:
        max_of_stack = max(max_of_stack, stack[j][0])
        j -= 1
    ans_i[i] = max_of_stack
for p in range(n):
    if array[p] < ans_i[d[p]]:
        array[p] = ans_i[d[p]]
print(*array)


# -*- coding: utf-8 -*-
# @Date    : 2019-08-01 06:48:30
# @Author  : raj lath (oorja.halt@gmail.com)
# @Link    : link
# @Version : 1.0.0

import sys
sys.setrecursionlimit(10**5+1)

inf     =  int(10 ** 20)
max_val =  inf
min_val = -inf

RW  = lambda : sys.stdin.readline().strip()
RI  = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]


nb = RI()
have = RMI()
nb_ops = RI()

curr = [-1] * nb
maxs = 0

ops = [RMI() for _ in range(nb_ops)][::-1]
for i in ops:
    if i[0] == 2:
        maxs = max(maxs, i[1])
    else:        
        if curr[i[1] - 1] == -1:
            curr[i[1] - 1] = max(maxs, i[2])
for i in range(nb)            :
    if curr[i] == -1:
        curr[i] = max(maxs, have[i])


print(*curr)

n=int(input())
a=[int(x) for x in input().split()]
t=q=int(input())
maxarr=[-1]*n
maxGlob=-1
quer=[]
while t>0:
    quer.append(tuple(map(int, input().split())))
    t-=1
for i in range(q-1,-1,-1):
    k=quer[i]
    if k[0]==2:
        maxGlob=max(maxGlob,k[1])
    else:
        if maxarr[k[1]-1]==-1:
            maxarr[k[1]-1]=max(k[2],maxGlob)

for i in range(n):
    if maxarr[i]==-1:
        maxarr[i]=(max(maxGlob,a[i]))
    
print(*maxarr)
    



n=int(input())
a=[int(x) for x in input().split()]
t=q=int(input())
maxarr=[-1]*n
maxGlob=-1
quer=[]
while t>0:
    quer.append([int(x) for x in input().split()])
    t-=1
for i in range(q-1,-1,-1):
    k=quer[i]
    if k[0]==2:
        maxGlob=max(maxGlob,k[1])
    else:
        if maxarr[k[1]-1]==-1:
            maxarr[k[1]-1]=max(k[2],maxGlob)
 
for i in range(n):
    if maxarr[i]==-1:
        maxarr[i]=(max(maxGlob,a[i]))
    
print(*maxarr)

n=int(input())
a=list(map(int,input().split()))
q=int(input())
arr=[]
for _ in range(q):
    arr.append(list(map(int, input().split())))
arr.reverse()
ans=[-1]*n
cur=0
for i in arr:
    if i[0]==2:
        cur=max(cur,i[1])
    else:
        if ans[i[1]-1]==-1:
            ans[i[1]-1]=max(cur,i[2])
for i in range(n):
    if ans[i]==-1:
        ans[i]=max(a[i],cur)
print(*ans)


R=lambda:map(int,input().split())
n = int(input ())
a=list(R())
q =int(input())
p=[]
ax= [-1]*n
for _ in range (q):p.append(list (R()))
temp=0
for i in  range(q-1,-1,-1):
    if p[i][0]==2:temp = max(temp,p[i][1])
    elif ax[p[i][1]-1]==-1:ax[p[i][1]-1] = max(temp,p[i][2])
for i in range (0,n):
    if ax[i]==-1:print(max(temp,a[i]),end=" ")
    else:print(ax[i],end=" ")


import sys

input = sys.stdin.readline
n = int(input())
li = list(map(int, input().split()))
check = [-1] * n
maxx = 0
for i in [input().split() for i in range(int(input()))][::-1]:
    if i[0] == '2':
        maxx = max(maxx, int(i[1]))
    else:
        if check[int(i[1]) - 1] == -1:
            check[int(i[1]) - 1] = max(int(i[2]), maxx)
for i in range(n):
    if check[i] == -1:
        check[i] = max(maxx, li[i])
print(*check)


import sys
read = sys.stdin.readline


n = int(read())
balance = list(map(int, read().split(" ")))
n_operations = int(read())

minis = []
next_mini = 0
changed_before = [0] * (len(balance)+1)

for n_op in range(n_operations):
    operation = list(map(int, read().split(" ")))
    if operation[0] == 1:
        x = operation[1] - 1
        balance[x] = operation[2]
        changed_before[x] = next_mini
    elif operation[0] == 2:
        minis.append(operation[1])
        next_mini += 1

if len(minis) > 0:
    max_mini = minis[-1]
    for m in range(1, len(minis) + 1):
        max_mini = max(max_mini, minis[m * -1])
        minis[m * -1] = max_mini

    for x in range(len(balance)):
        cb = changed_before[x]
        if cb < next_mini:
            balance[x] = max(minis[cb], balance[x])
        balance[x] = str(balance[x])
else:
    for x in range(len(balance)):
        balance[x] = str(balance[x])

print(" ".join(balance))

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
q = int(input())
a2 = [-1]*len(a)
arr = [None]*q
pay = [-1]*q
for i in range(q):
    b = input().split()
    if len(b) == 2:
        pay[i] = int(b[1])
    else:
        arr[i] = int(b[1])
        a2[arr[i]-1] = int(b[2])
        
pay_max = max(pay)
pay_maxi = q - pay[::-1].index(pay_max) - 1
a = [pay_max if x<pay_max else x for x in a]
m = [0]*q
ma = -1
for i in range(q-1,-1,-1):
    if pay[i] != -1:
        ma = max(ma,pay[i])
    m[i] = ma
for i in range(q):
    if arr[i]:
        if i > pay_maxi:
            a[arr[i]-1] = max(a2[arr[i]-1], m[i])
        else:
            a[arr[i]-1] = max(a2[arr[i]-1], pay_max)
print(*a)        
#print(' '.join([str(x) for x in a]))


R=lambda:map(int,input().split())
n=int(input())
r=[-1]*n
a=*zip(r,range(1,n+1),R()),*([*R()]for _ in[0]*int(input()))
m=0
for t,p,*x in a[::-1]:
 if t>1:m=max(m,p)
 elif r[p-1]<0:r[p-1]=max(x[0],m)
print(*r)

R=lambda:map(int,input().split())
n=int(input())
a=*zip([1]*n,range(1,n+1),R()),*([*R()]for _ in[0]*int(input()))
r=[-1]*n
m=0
for t,p,*x in a[::-1]:
 if t>1:m=max(m,p)
 elif r[p-1]<0:r[p-1]=max(x[0],m)
print(*r)

n = int(input())
balance = list(map(int, input().split()))
q = int(input())
log = [list(map(int, input().split())) for i in range(q)]

ind_of_last_operation = [None] * n
max_pay = 0
ind_of_max_payment = None
payments = []
payments_id = []

for i in range(q):
    if log[i][0] == 1:
        ind_of_last_operation[log[i][1] - 1] = i

for i in range(q):
    if log[i][0] == 2:
        ind_of_last_payment = i
        last_payment = log[i][1]
        if log[i][1] > max_pay:
            max_pay = log[i][1]

max_pay_for_moment = [0] * (q + 1)
for j in range(q - 1, -1, -1):
    if log[j][0] == 2:
        max_pay_for_moment[j] = max(log[j][1], max_pay_for_moment[j + 1])
    else:
        max_pay_for_moment[j] = max_pay_for_moment[j + 1]

for i in range(n):
    if ind_of_last_operation[i] == None:
        if balance[i] < max_pay:
            balance[i] = max_pay
    else:
        if max_pay_for_moment[ind_of_last_operation[i] + 1] > log[ind_of_last_operation[i]][2]:
            balance[i] = max_pay_for_moment[ind_of_last_operation[i] + 1]
        else:
            balance[i] = log[ind_of_last_operation[i]][2]

print(*balance)

n, a, q = int(input()), [*list(map(int, input().split()))], int(input())
ops = []

for i in range(q):
  t, *b = list(map(int, input().split()))
  ops.append((t, b))

b = [-1] * n
m = -1
for op, ar in reversed(ops):
  if op == 2:
    m = max(m, ar[0])
  else:
    p, x = ar
    p -= 1
    if b[p] == -1:
      b[p] = max(x, m)

print(' '.join(str(bi if bi != -1 else max(m, ai))for ai,bi in zip(a,b)))


from bisect import bisect_right
n = int(input())
A = list(map(int, input().split()))
B = [0] * n
C = []
for i in range(int(input())):
    w = list(map(int, input().split()))
    if w[0] == 1:
        A[w[1] - 1] = w[2]
        B[w[1] - 1] = i
    else:
        C.append((i, w[1]))
sC = [0]
for i in range(len(C) - 1, -1, -1):
    sC.append(max(sC[-1], C[i][1]))
sC = sC[::-1]
for i in range(n):
    A[i] = max(A[i], sC[bisect_right(C, (B[i], 0))])
print(*A)

n = int(input().strip())
a = list(map(int, input().split()))
q = int(input().strip())
queries = []
last_balance = [-1]*n
last_balance_id = [-1]*n

for i in range(q):
    query = list(map(int, input().split()))
    queries.append(query)
    if query[0]==1:
        p = query[1]-1
        last_balance[p] = query[2]
        last_balance_id[p] = i


#print(last_balance)
#print(last_balance_id)

max_pay = [0]*(q+1)
for i in range(q-1,-1,-1):
    query = queries[i]
    if query[0]==2:
        max_pay[i]=max(query[1], max_pay[i+1])
    else:
        max_pay[i]=max_pay[i+1]

#print(max_pay)

for p in range(n):
    #print("person: ",p)
    if last_balance_id[p]>=0:
        id = last_balance_id[p]
        pay = max_pay[id]
        #print(id, pay)
        a[p] = max(pay, last_balance[p])
    else:
        a[p] = max(a[p], max_pay[0])

print(" ".join([str(x) for x in a]))

n = int(input())
a = list(map(int, input().split()))
q = int(input())
s = [0 for i in range(len(a))]
f = [0 for i in range(q)]

for i in range(q):
    r = list(map(int, input().split()))
    if(r[0] == 1):
        s[r[1]-1] = i
        a[r[1]-1] = r[2]
    else:
        f[i] = r[1]

for i in reversed(range(0,q-1)):
    f[i] = max(f[i], f[i+1])

for i in range(n):
    a[i] = max(a[i], f[s[i]])

print(*a)

n = int(input())
sp = list(map(int, input().split()))

m = int(input())
pos = [-1] * (n + 1)
m1 = 0
mem = []
for i in range(m):
    sp1 = list(map(int, input().split()))
    mem.append(sp1)
    if sp1[0] == 1:
        sp[sp1[1] - 1] = sp1[2]
        pos[sp1[1] - 1] = i
    else:
        m1 = max(m1, sp1[1])
        
maxs = [-1] * (m + 1)

for i in range(m - 1, -1, -1):
    sp1 = mem[i]
    
    if (sp1[0] == 2):
        if (i == m - 1 or sp1[1] > maxs[i + 1]):
            maxs[i] = sp1[1]
        else:
            maxs[i] = maxs[i + 1]
    else:
        maxs[i] = maxs[i + 1]
for i in range(n):
    if pos[i] != -1 and sp[i] < maxs[pos[i]]:
        sp[i] = maxs[pos[i]]
    elif pos[i] == -1:
        sp[i] = max(sp[i], maxs[0])
print(*sp)


n=int(input())
a=list(map(int,input().split()))
q=int(input())
arr=[]
for _ in range(q):
    arr.append(list(map(int, input().split())))
arr.reverse()
ans=[-1]*n
cur=0
for i in arr:
    if i[0]==2:
        cur=max(cur,i[1])
    else:
        if ans[i[1]-1]==-1:
            ans[i[1]-1]=max(cur,i[2])
for i in range(n):
    if ans[i]==-1:
        ans[i]=max(a[i],cur)
print(*ans)


from sys import stdin
input = stdin.readline

n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)][::-1]
res, curr = [-1] * n, 0
for q in queries:
    if q[0] == 1:
        if res[q[1]-1] == -1:
            res[q[1]-1] = max(q[2], curr)
    else:
        curr = max(curr, q[1])
for i in range(n):
    if res[i] == -1:
        res[i] = max(curr, arr[i])
res = [str(q) for q in res]
print(' '.join(res))