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
import java.lang.*;
import java.math.*;
import java.util.*;
import java.io.*;

public class Main {
    void solve() {
        int n=ni();
        a=new int[n+1];
        for(int i=1;i<=n;i++) a[i]=ni();
        tree=new int[4*n+1];
        lazy=new int[4*n+1];
        Arrays.fill(lazy,-1);
        build(1,1,n);
        int q=ni();
        while(q-->0){
            int t=ni();
            if(t==1){
                int p=ni(),x=ni();
                update1(1,1,n,p,x);

            }else {
                int x=ni();
                update2(1,1,n,1,n,x);
            }
        }
        for(int i=1;i<=n;i++) pw.print(query(1,1,n,i)+" ");
        pw.println("");
    }
    int a[];
    int tree[];
    int lazy[];
    void build(int id,int l,int r){
        if(l==r){
            tree[id]=a[l];
        }else {
            int mid=(l+r)>>1;
            build(2*id,l,mid);
            build(2*id+1,mid+1,r);
            tree[id]=Math.min(tree[2*id],tree[2*id+1]);
        }
    }
    void update1(int id,int l,int r,int x,int val){
        push(id,l,r);
        if(l==r){
            tree[id]=val;
        }else {
            int mid=(l+r)>>1;
            if(x<=mid) update1(2*id,l,mid,x,val);
            else update1(2*id+1,mid+1,r,x,val);
            tree[id]=Math.min(tree[2*id],tree[2*id+1]);
        }
    }
    void update2(int id,int x,int y,int l,int r,int val){
        push(id,l,r);
        if(r<x || l>y) return;
        if(x<=l && r<=y){
            tree[id]=Math.max(tree[id],val);
            if(l!=r){
                lazy[2*id]=Math.max(lazy[2*id],val);
                lazy[2*id+1]=Math.max(lazy[2*id+1],val);

            }
            return;
        }
        int mid=(l+r)>>1;
        update2(2*id,x,y,l,mid,val);
        update2(2*id+1,x,y,mid+1,r,val);
        tree[id]=Math.min(tree[2*id],tree[2*id+1]);
    }
    int query(int id,int l,int r,int x){
        push(id,l,r);
        if(l==r) return tree[id];
        else {
            int mid=(l+r)>>1;
            if(x<=mid)return query(2*id,l,mid,x);
            else return query(2*id+1,mid+1,r,x);
        }
    }
    void push(int id,int l,int r){
        if(lazy[id]==-1) return;
        tree[id]=Math.max(tree[id],lazy[id]);
        if(l!=r){
            lazy[2*id]=Math.max(lazy[2*id],lazy[id]);
            lazy[2*id+1]=Math.max(lazy[2*id+1],lazy[id]);

        }
        lazy[id]=-1;
    }
    long M = (long) 1e9 + 7;
    InputStream is;
    PrintWriter pw;
    String INPUT = "";

    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
        if (!INPUT.isEmpty()) tr(System.currentTimeMillis() - s + "ms");


    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++) map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void tr(Object... o) {
        if (INPUT.length() > 0) System.out.println(Arrays.deepToString(o));
    }

}