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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.nio.file.Paths;
import java.util.*;
public class Main extends PrintWriter {
    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));Main () { super(System.out); }public static void main(String[] args) throws IOException{ Main  d1=new Main   ();d1.main();d1.flush(); }

    void main() throws IOException {
        StringBuilder sb = new StringBuilder();
        StringBuilder sb1 = new StringBuilder();
        int t = 1;
//        t = i(s()[0]);
       while (t-- > 0) {
                String[] s1 = s(); int n = i(s1[0]); int[] a=new int[n]; arri(a, n);
                int q = i(s()[0]);
                Pair[] p = new Pair[q];
                int qq = q;
                 int[] suf = new int[q];
                int i = 0;
                int[] update = new int[n];
                while(q-- > 0){
                    String[] s3 = s();
                    int type = i(s3[0]);
                    if(type == 1){
                        int ind = i(s3[1]) - 1;
                        int val = i(s3[2]);
                        p[i] = new Pair(1, ind, val);
                        a[ind] = val;
                        update[ind] = i;
                    }else{
                        p[i] = new Pair(2, 0, i(s3[1]));
                    }
                    i++;
                }
                for(i = qq - 1; i >= 0; i--){
                    if(i == qq - 1){
                        if(p[i].type == 2) {
                            suf[i] = p[i].x;
                        }else{
                            suf[i] = 0;
                        }
                    }else{
                        if(p[i].type == 2) {
                            suf[i] = Math.max(suf[i + 1], p[i].x);
                        }else{
                            suf[i] = Math.max(suf[i + 1], 0);
                        }
                    }
                }
                for( i=0;i<n;i++){
                   sb.append(Math.max(a[i], suf[update[i]]) + " ");
                }


        }
        System.out.println(sb);
    }

    static String[] s() throws IOException { return s.readLine().trim().split("\\s+"); }
    static int i(String ss) {return Integer.parseInt(ss); }
    static long l(String ss) {return Long.parseLong(ss); }
    public void arr(long[] a,int n) throws IOException {String[] s2=s();for(int i=0;i<n;i++){ a[i]=l(s2[i]); }}
    public void arri(int[] a,int n) throws IOException {String[] s2=s();for(int i=0;i<n;i++){ a[i]=i(s2[i]); }}
}class Pair{
    int type; int p ; int x;
    public Pair(int type, int p, int x){
        this.type = type;
        this.p = p;
        this.x = x;
    }
}


