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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;



public class bits {
    public static class FastReader {
			BufferedReader br;
			StringTokenizer st;
			//it reads the data about the specified point and divide the data about it ,it is quite fast
			//than using direct 
	 
			public FastReader() {
				br = new BufferedReader(new InputStreamReader(System.in));
			}
	 
			String next() {
				while (st == null || !st.hasMoreTokens()) {
					try {
						st = new StringTokenizer(br.readLine());
					} catch (Exception r) {
						r.printStackTrace();
					}
				}
				return st.nextToken();
			}
	 
			int nextInt() {
				return Integer.parseInt(next());//converts string to integer
			}
	 
			double nextDouble() {
				return Double.parseDouble(next());
			}
	 
			long nextLong() {
				return Long.parseLong(next());
			}
	 
			String nextLine() {
				String str = "";
				try {
					str = br.readLine();
				} catch (Exception r) {
					r.printStackTrace();
				}
				return str;
			}
		}
		
		public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	    
	static int ans=0;static int ar[]=new int[501];
static void bit(String a,String b)
{int ct=0;
	for(int i=0;i<a.length();i++)
	{
		if(a.charAt(i)=='1'||b.charAt(i)=='1')
			ct++;
	}
	ans=Math.max(ans, ct);
	ar[ct]++;
	
}
static class Pair implements Comparable<Pair>{
    int x;int y;
    Pair(int x,int y){
        this.x=x;
        this.y=y;
      //  this.i=i;
    }
	@Override
	public int compareTo(Pair o) {
		// TODO Auto-generated method stub
		return x-o.x;
		
	}
}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
ArrayList<Integer>list=new ArrayList<Integer>();
		FastReader in=new FastReader();
		Stack<Integer>stack=new Stack<Integer>();
	int n=in.nextInt();
	int a[]=new int[n];
	for(int i=0;i<n;i++)
		a[i]=in.nextInt();
	int q=in.nextInt();int pos[]=new int[n];
	int ans=0;int u[]=new int[q+5];int r=0;int s=q;
	while(q-->0)
	{
		int t=in.nextInt();
		if(t==2)
		{int y=in.nextInt();
			
		u[r]=y;
			ans=Math.max(ans, y);
		}
		else
		{
			int p=in.nextInt();
			int x=in.nextInt();
			a[p-1]=x;
			pos[p-1]++;
			map.put(p-1, r);
		}
		r++;
	}
	
	for(int i=s-2;i>=0;i--)
	{
		if(u[i]>u[i+1])
		{
			u[i]=u[i];
		}
		else u[i]=u[i+1];
			
	}
	for(int i=0;i<n;i++)
	{
		if(pos[i]>0)
			System.out.print(Math.max(a[i], u[map.get(i)+1])+" ");
		else
		{ if(a[i]<ans)
			System.out.print(ans+" ");
		else
			System.out.print(a[i]+" ");
			}
	}
	
			
	
		
	}

}
