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
def main():

    import sys, math
    #from bisect import bisect_left as bl, bisect_right as br, insort
    #from heapq import heapify, heappush, heappop
    #from collections import defaultdict as dd, deque, Counter
    #from itertools import permutations,combinations
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    def construct_sum(a, n):
        for i in range(n):
            segtree[n + i] = a[i]
        for i in range(n - 1, 0, -1):
            segtree[i] = max(segtree[2 * i], segtree[2 * i + 1])

    def update_sum(pos, x):
        pos += n - 1
        segtree[pos] = x
        while (pos > 1):
            pos >>= 1
            segtree[pos] = max(segtree[2 * pos], segtree[2 * pos + 1])

    def getSum(l, r,n):
        l += n - 1
        r += n - 1
        s = 0
        while (l <= r):
            if l & 1:
                s = max(s,segtree[l])
                l += 1
            if (r + 1) & 1:
                s = max(s,segtree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return s

    n = int(data())
    a = list(mdata())
    v=[0]*n
    x=[]
    cnt=0
    for i in range(int(data())):
        l=mdata()
        if len(l)==2:
            x.append(l[1])
            cnt+=1
        else:
            a[l[1]-1]=l[2]
            v[l[1]-1]=cnt
    segtree = [0] * (2 * len(x))
    construct_sum(x,len(x))
    ans=[0]*n
    for i in range(n):
        ans[i]=max(a[i],getSum(v[i]+1,len(x),len(x)))
    print(*ans)


if __name__ == '__main__':
    main()
