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

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		FastReader sc=new FastReader();
		int n=sc.I();
		int[] a=new int[n];
		for(int i=0;i<n;i++)
		{
		    a[i]=sc.I();
		}
		int q=sc.I();
	    int[] c=new int[n];
	    int[] d=new int[q];
	    for(int i=0;i<n;i++)
	    c[i]=-1;
	    for(int k=0;k<q;k++)
	    {
	        int o=sc.I();
	        if(o==1)
	        {
	            int p=sc.I();
	            a[p-1]=sc.I();
	            c[p-1]=k;
	        }
	        else
	        {
	            d[k]=sc.I();
	        }
	    }
	    for(int i=q-2;i>=0;i--)
	    {
	        d[i]=(d[i]>d[i+1])?d[i]:d[i+1];
	    }
		for(int i=0;i<n;i++){
		    if(c[i]==-1){
		        if(d[0]>a[i])
		System.out.print(d[0]+" ");
		else
		System.out.print(a[i]+" ");
		    }
		    else 
		    {
		        if(d[c[i]]>a[i])
		        System.out.print(d[c[i]]+" ");
		else
		System.out.print(a[i]+" ");
		    }
		}
	 }
	 static int binarysearch(int x,int[] b,int n)
	 {
	     int l=0,r=n-1,m=(l+r)/2;
	     if(x<b[0]||x>b[r])
	     return -1;
	     while(l<=r)
	     {
	         m=(l+r)/2;
	         if(b[m]==x)
	         return m;
	         if(b[m]>x)
	         r=m-1;
	         else
	         l=m+1;
	     }
	     return -1;
	 }
	 static int lower(int x,int b[],int n)
	 {
	     if(x<b[0])
	     return -1;
	     else if(x==b[0])
	     return 0;
	     if(x>=b[n-1])
	     return n-1;
	     int l=0,r=n-1,m=(l+r)/2;
	     while(l<=r)
	     {
	         m=(l+r)/2;
	         if(b[m]<=x&&b[m+1]>x)
	         return m;
	         else if(b[m]>x&&b[m-1]<=x)
	         return m-1;
	         if(b[m]>x)
	         r=m-1;
	         else if(b[m]<x)
	         l=m+1;
	     }
	     return -1;
	 }
	 static int upper(int x,int b[],int n)
	 {
	     if(x<=b[0])
	     return 0;
	     else if(x==b[n-1])
	     return n-1;
	     if(x>b[n-1])
	     return -1;
	     int l=0,r=n-1,m=(l+r)/2;
	     while(l<=r)
	     {
	         m=(l+r)/2;
	         if(b[m]<x&&b[m+1]>=x)
	         return m+1;
	         else if(b[m]>=x&&b[m-1]<x)
	         return m;
	         if(b[m]>x)
	         r=m-1;
	         else if(b[m]<x)
	         l=m+1;
	     }
	     return -1;
	 }
	 
	 static long power(long x, long y, long p) 
    { 
        // Initialize result 
        long res = 1;      
         
        // Update x if it is more   
        // than or equal to p 
        x = x % p;  
      
        while (y > 0) 
        { 
            // If y is odd, multiply x 
            // with result 
            if((y & 1)==1) 
                res = (res * x) % p; 
      
            // y must be even now 
            // y = y / 2 
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
    } 
	  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            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 I() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long L() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double D() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    static int gcd(int a,int b)
		{
		    if(a%b==0)
		    return b;
		    return gcd(b,a%b);
		}
	static float power(float x, int y) 
    { 
        float temp; 
        if( y == 0) 
            return 1; 
        temp = power(x, y/2);  
          
        if (y%2 == 0) 
            return temp*temp; 
        else
        { 
            if(y > 0) 
                return x * temp * temp; 
            else
                return (temp * temp) / x; 
        } 
    } 
    static long pow(int a,int b)
    {
        long result=1;
        if(b==0)
        return 1;
        long x=a;
        while(b>0)
        {
            if(b%2!=0)
            result*=x;
            
            x=x*x;
            b=b/2;
        }
        return result;
    }
    
    static ArrayList<Integer> sieveOfEratosthenes(int n) 
    { 
        ArrayList<Integer> arr=new ArrayList<Integer>();
        boolean prime[] = new boolean[n+1]; 
        for(int i=2;i<n;i++) 
            prime[i] = true; 
          
        for(int p = 2; p*p <=n; p++) 
        { 
            if(prime[p] == true) 
            { 
                arr.add(p);
                for(int i = p*p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
        return arr;
    } 
}