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
//package test;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
 
public class starter {
		
		public static void main ( String args[] )
			throws Exception 
		{
			Scanner conio = new Scanner ( System.in ) ;
			//Scanner conio = new Scanner ( new File ( "battery.in" ) );
			
			int n = conio.nextInt() ;
			ArrayList<Integer> holder = new ArrayList<>() ;
			int last[] = new int [n] ;
			Arrays.fill(last, -1 );
			
			
			int citz [] = new int [n] ;
			
			for ( int i = 0 ; i < n ; ++i )
				citz[i] = conio.nextInt() ;
			
			int events = conio.nextInt() ;
			int type , person , money , min ;
			
			for ( int i = 0 ; i < events ; ++i )
			{
				type = conio.nextInt() ;
				
				if ( type == 1 )
				{
					person = conio.nextInt() ;
					money = conio.nextInt() ;
					
					citz[person-1] = money ;
					last[person-1] = holder.size();
				}
				
				else if ( type == 2 )
				{
					min = conio.nextInt() ;
					holder.add(min) ; 
				}
			}
			
			// now update all the citizens 
			
			int max ; 
					
			for ( int i = holder.size() - 2 ; i >= 0 ; --i )
			{
				holder.set( i , ( int ) Math.max ( holder.get(i) , holder.get( i + 1 ) ) ) ; 
			}
			
			
			for ( int i = 0 ; i < n ; ++i )
			{
				if ( last[i] == -1 )
					max = holder.size() > 0 ? holder.get(0) : 0 ; 
				else if ( last[i] == holder.size() )
					max = 0 ;
				else
					max = holder.get(last[i]) ; 
			
				citz[i] = ( int ) Math.max( citz[i] , max ) ; 
			}
			
			
			for ( int i = 0 ; i < n ; ++i )
				System.out.print(citz[i] + " " );
			
			conio.close(); 
		}				
} 