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


// @author : Dinosparton 

public class test {
	 
	   static class Pair{ 
		   long x;
		   long y;
		   
		   Pair(long x,long y){ 
			   this.x = x;
			   this.y = y;
			   
		   }
	   }
	  
	   static class Sort implements Comparator<Pair>
	   {

	       @Override
	       public int compare(Pair a, Pair b)
	       {
	           if(a.x!=b.x)
	           {
	               return (int)(a.x - b.x);
	           }
	           else
	           {
	               return (int)(a.y-b.y);
	           }
	       }
	   }
	   
	   static class Compare { 
		   
		     void compare(Pair arr[], int n) 
		    { 
		        // Comparator to sort the pair according to second element 
		        Arrays.sort(arr, new Comparator<Pair>() { 
		            @Override public int compare(Pair p1, Pair p2) 
		            { 
		            	if(p1.x!=p2.x) {
		                return (int)(p1.x - p2.x); 
		            	}
		            	else { 
		            		return (int)(p1.y - p2.y);
		            	}
		            } 
		        }); 
		  
//		        for (int i = 0; i < n; i++) { 
//		            System.out.print(arr[i].x + " " + arr[i].y + " "); 
//		        } 
//		        System.out.println(); 
		    } 
		} 
	 
	   static class Scanner {
	        BufferedReader br;
	        StringTokenizer st;
	 
	        public Scanner()
	        {
	            br = new BufferedReader(
	                new InputStreamReader(System.in));
	        }
	 
	        String next()
	        {
	            while (st == null || !st.hasMoreElements()) {
	                try {
	                    st = new StringTokenizer(br.readLine());
	                }
	                catch (IOException e) {
	                    e.printStackTrace();
	                }
	            }
	            return st.nextToken();
	        }
	 
	        int nextInt() { return Integer.parseInt(next()); }
	 
	        long nextLong() { return Long.parseLong(next()); }
	 
	        double nextDouble()
	        {
	            return Double.parseDouble(next());
	        }
	 
	        String nextLine()
	        {
	            String str = "";
	            try {
	                str = br.readLine();
	            }
	            catch (IOException e) {
	                e.printStackTrace();
	            }
	            return str;
	        }
	    }
	
	  
	   static class triplet{
		   
		   int type;
		   int p;
		   long x;
		   
		   triplet(int type,int p,long x){
			   
			   this.type = type;
			   this.p = p;
			   this.x = x;
		   }
		   
	   }
	   public static void main(String args[]) throws Exception { 
		
		   
		   Scanner sc = new Scanner();
		   StringBuilder res = new StringBuilder();
		  
		   int tc = 1;
		  
		   while(tc-->0) { 
			
                int n = sc.nextInt();
                
                long a[] = new long[n];
                
                for(int i=0;i<n;i++) {
                	a[i] = sc.nextLong();
                }
                
                int q = sc.nextInt();
                
                long set[] = new long[n];
                
                for(int i=0;i<n;i++) {
                	set[i] = -1;
                }
                int set_index[] = new int[n];
                triplet query[] = new triplet[q];
                
                for(int i=0;i<q;i++) {
                	
                	int type = sc.nextInt();
                	
                	if(type==1) {
                		
                		int p = sc.nextInt();
                		long x = sc.nextLong();
                		
                		query[i] = new triplet(type,p,x);
                		
                		set[p-1] = x;
                		set_index[p-1] = i;
                	}
                	else {
                		
                		long x = sc.nextLong();
                		
                		
                		query[i] = new triplet(type,0,x);
                	}
                }
                
                long range[] = new long[q];
                long max = 0;
                
                for(int i=q-1;i>=0;i--) {
                	
                	if(query[i].type==2) {
                		max = Math.max(max, query[i].x);
                	}
                	
                	range[i] = max;
                }
                
                for(int i=0;i<n;i++) {
                	
                	if(set[i]!=-1) {
                		a[i] = set[i];
                	}
                	
                	a[i] = Math.max(a[i], range[set_index[i]]);
                }
                
                for(int i=0;i<n;i++) {
                	res.append(a[i]+" ");
                }
		   }
			System.out.println(res);
		   
	   }
}  




