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.*;
public class Codechef
{       static PrintWriter out=new PrintWriter(System.out);static FastScanner in = new FastScanner(System.in);static class FastScanner {BufferedReader br;StringTokenizer stok;FastScanner(InputStream is) {br = new BufferedReader(new InputStreamReader(is));}
        String next() throws IOException {while (stok == null || !stok.hasMoreTokens()) {String s = br.readLine();if (s == null) {return null;}
                stok = new StringTokenizer(s);}return stok.nextToken();}
        int ni() throws IOException {return Integer.parseInt(next());}long nl() throws IOException {return Long.parseLong(next());}double nd() throws IOException {return Double.parseDouble(next());}char nc() throws IOException {return (char) (br.read());}String ns() throws IOException {return br.readLine();}
        int[] nia(int n) throws IOException{int a[] = new int[n];for (int i = 0; i < n; i++)a[i] = ni();return a;}long[] nla(int n) throws IOException {long a[] = new long[n];for (int i = 0; i < n; i++)a[i] = nl();return a;}
        double[] nda(int n)throws IOException {double a[] = new double[n];for (int i = 0; i < n; i++)a[i] = nd();return a;}int [][] imat(int n,int m) throws IOException{int mat[][]=new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++)mat[i][j]=ni();}return mat;}
    }
	static long mod=Long.MAX_VALUE;
	public static void main (String[] args) throws java.lang.Exception
	{   int i=0,j=0;
	    int n=in.ni();
	    int a[]=in.nia(n);
	    int q=in.ni();
	    int temp[][]=new int[2][n];
	    for(i=0;i<n;i++)
        {   temp[0][i]=a[i];
            temp[1][i]=0;
        }
        int min=0;
        int temp2[]=new int[q+1];
        for(i=0;i<=q;i++)
            temp2[i]=-1;
        for(i=1;i<=q;i++)
        {   int z=in.ni();
            if(z==1)
            {  // out.println("type1");
                int p=in.ni()-1;
                int Q=in.ni();
                temp[0][p]=Q;
                temp[1][p]=i;
            }
            else
            {    temp2[i]=in.ni();
                //out.println("type2"+" i="+i);
            }
        }
        /*
        for(i=0;i<=q;i++)
            out.print(temp2[i]+" ");
        out.println();    
          */      
        for(i=q-1;i>=0;i--)
            temp2[i]=Math.max(temp2[i+1],temp2[i]);
        for(i=0;i<n;i++)
        {   out.print(Math.max(temp[0][i],temp2[temp[1][i]])+" ");
        
        }    
        out.close();
	}
	public static int first(int arr[], int low, int high, int x, int n) 
    { 
        if(high >= low) 
        { 
            int mid = low + (high - low)/2; 
            if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x) 
                return mid; 
             else if(x > arr[mid]) 
                return first(arr, (mid + 1), high, x, n); 
            else
                return first(arr, low, (mid -1), x, n); 
        } 
    return -1; 
    } 
    public static int last(int arr[], int low, int high, int x, int n) 
    { 
        if (high >= low) 
        { 
            int mid = low + (high - low)/2; 
            if (( mid == n-1 || x < arr[mid+1]) && arr[mid] == x) 
                 return mid; 
            else if (x < arr[mid]) 
                return last(arr, low, (mid -1), x, n); 
            else
                return last(arr, (mid + 1), high, x, n); 
        } 
    return -1; 
    } 
    
}