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
/* Rajkin Hossain */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class D{
   
    FastInput k = new FastInput(System.in);
    //FastInput k = new FastInput("/home/rajkin/Desktop/input.txt");
    FastOutput z = new FastOutput();
    
    int n, q;
    int [] y;
    
    boolean [] setDone;
    
    ArrayList<Triple> queries;
     
    void startAlgorithm() {
    	
    	int maxBalance = -1;
    	
    	for(int i = queries.size()-1; i>=0; i--) {
    		Triple t = queries.get(i);
    		if(t.queryType == 1) {
    			if(!setDone[t.index]) {
    				setDone[t.index] = true;
    				y[t.index] = Math.max(t.balance, maxBalance);
    			}
    		}
    		else {
    			maxBalance = Math.max(t.balance, maxBalance);
    		}
    	}
    	
    	for(int i = 1; i<=n; i++) {
    		if(!setDone[i]) {
    			y[i] = Math.max(y[i], maxBalance);
    		}
    	}
    	
    	for(int i = 1; i<=n; i++) {
    		z.print(y[i]+" ");
    	}
    	
    	z.println();
    }
    
    void startProgram() {
    	while(k.hasNext()) {
    		n = k.nextInt();
    		y = new int[n+1];
    		
    		setDone = new boolean[n+1];
    		
    		for(int i = 1; i<=n; i++) {
    			y[i] = k.nextInt();
    		}
    		
    		q = k.nextInt();
    		queries = new ArrayList<>();
    		while(q-->0) { 
    			int queryType = k.nextInt();
    			if(queryType == 1) {
    				queries.add(new Triple(1, k.nextInt(), k.nextInt()));
    			}
    			else {
    				queries.add(new Triple(2, k.nextInt()));
    			}
    		}
    		
    		startAlgorithm();
    	}
    	
    	z.flush();
    	System.exit(0);
    }
    
    class Triple{
    	int queryType;
    	int index;
    	int balance;
    	
		public Triple(int queryType, int index, int balance) {
			this.queryType = queryType;
			this.index = index;
			this.balance = balance;
		}
		
		public Triple(int queryType, int balance) {
			this.queryType = queryType;
			this.balance = balance;
		}
    }
    
    public static void main(String [] args) throws IOException {
        new Thread(null, new Runnable(){
            public void run(){
            	try{ 
            		new D().startProgram();
            	}
            	catch(Exception e){
            		e.printStackTrace();
            	}
            }
        },"Main",1<<28).start();
    }
    

    /* MARK: FastInput and FastOutput */
 
    class FastInput {
        BufferedReader reader;
        StringTokenizer tokenizer;
 
        FastInput(InputStream stream){
            reader = new BufferedReader(new InputStreamReader(stream));
        }
       
        FastInput(String path){
            try {
                reader = new BufferedReader(new FileReader(path));
            } catch (FileNotFoundException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            tokenizer = null;
        }
 
        String next() {
            return nextToken();
        }
       
        String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
           
            return null;
        }
 
        boolean hasNext(){
            try {
                return reader.ready();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            return false;
        }
 
        String nextToken() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                String line = null;
                try {
                    line = reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null) {
                    return null;
                }
                tokenizer = new StringTokenizer(line);
            }
            return tokenizer.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(nextToken());
        }
       
        long nextLong() {
            return Long.valueOf(nextToken());
        }
    }
 
    class FastOutput extends PrintWriter {
		FastOutput() {
			super(new BufferedOutputStream(System.out)); 
		}
		
		public void debug(Object...obj) {
		    System.err.println(Arrays.deepToString(obj));
		}
    }
}
