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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

//import hacker51.FastReader;

public class two_pointers_method {
	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 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; 
        }
    }
	
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
	FastReader s=new FastReader();
int n=s.nextInt();
long[] a=new long[n];
for(int i=0;i<n;i++) {
	a[i]=s.nextLong();
}
int[] f1=new int[n];
for(int i=0;i<n;i++) {
	f1[i]=-1;
}
int q=s.nextInt();
int j=0;
long[] f2=new long[q];
for(int i=0;i<q;i++) {
	f2[i]=Long.MIN_VALUE;
}
long max=Long.MIN_VALUE;
while(j<q) {
	int x=s.nextInt();
	if(x==1) {
		int y=s.nextInt();
		y--;
		long val=s.nextLong();
		a[y]=val;
		f1[y]=j;
	}else {
		long val=s.nextLong();
		max=Math.max(val, max);
		f2[j]=val;
	}
	j++;
}
for(int i=q-2;i>=0;i--) {
	f2[i]=Math.max(f2[i+1], f2[i]);
}
for(int i=0;i<n;i++) {
	if(f1[i]==-1) {
		a[i]=Math.max(max, a[i]);
	}else {
		a[i]=Math.max(a[i], f2[f1[i]]);
	}
}
for(int i=0;i<n;i++) {
	out.print(a[i]+" ");
}
	
	out.close();
	}
//	 static class pair implements Comparable<pair> {
//         private  long len;
//         private  long beauty;
//         public pair(long len, long beauty) {
//             this.len = len;
//             this.beauty = beauty;
//         }
//
//         @Override
//         public int compareTo(pair item) {
//             return Long.compare(item.beauty, this.beauty);
//         }
//     }
//
// 
	public static int lower_bound(int[] a ,int n,long x) {
		int l=-1;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]<x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return l;
				
	}
	public static int upper_bound(int[] a ,int n,int x) {
		int l=-1;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]<=x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return r;
				
	}

//	static class pair{
//		private long a;
//		private long b;
//		pair(long a,long b){
//			this.a=a;
//			this.b=b;
//		}
//	}
	static class pair2 implements Comparable<pair2>{
		private long a;
		private int b;
		pair2(long a,int b){
			this.a=a;
			this.b=b;
		}
		public int compareTo(pair2 p) {
			return Long.compare(this.a,p.a);
		}
	}
	public static int longest_Common_Substring_using_top_down(String str1,String str2,int n,int m) {
		int[][] dp=new int[n+1][m+1];
		int max=Integer.MIN_VALUE;
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				if(str1.charAt(i-1)==str2.charAt(j-1)) {
					dp[i][j]=1+dp[i-1][j-1];
					max=Math.max(max, dp[i][j]);
				}else {
					dp[i][j]=0;//since substring are continuous
				}
			}
		}
		
		return max;
	}
//	public static pair[] merge_sort(pair[] A, int start, int end) {
//		if (end > start) {
//			int mid = (end + start) / 2;
//			pair[] v = merge_sort(A, start, mid);
//			pair[] o = merge_sort(A, mid + 1, end);
//			return (merge(v, o));
//		} else {
//			pair[] y = new pair[1];
//			y[0] = A[start];
//			return y;
//		}
//	}
//	public static pair[] merge(pair a[], pair b[]) {
////		int count=0;
//		pair[] temp = new pair[a.length + b.length];
//		int m = a.length;
//		int n = b.length;
//		int i = 0;
//		int j = 0;
//		int c = 0;
//		while (i < m && j < n) {
//			if (a[i].a < b[j].a) {
//				temp[c++] = a[i++];
//			
//			} else {
//				temp[c++] = b[j++];
//			}
//		}
//		while (i < m) {
//			temp[c++] = a[i++];
//		}
//		while (j < n) {
//			temp[c++] = b[j++];
//		}
//		return temp;
//	}
	static boolean ok(long n) {
		long sum=0;
		while(n>0) {
			sum+=n%10;
			n/=10;
		}
		return (sum==10);
	}
	static long get1(long n) {
		long f=0;
//		long f2=9;
		while(n>0) {
			f=Math.max(f, n%10);
			n/=10;
		}
		return f;
	}
	static long get2(long n) {
		long f=9;
//		long f2=9;
		while(n>0) {
			f=Math.min(f, n%10);
			n/=10;
		}
		return f;
	}
	static long get(long n,long k,long count) {
		if(count==k) {
			return n;
		}else {
			long t1=get1(n);
			long t2=get2(n);
			long y=n+t1*t2;
			return get(y,k,count+1);
		}
	}
	
	
	public static int lower_bound(ArrayList<Integer> a ,int n,int x) {
		int l=-1;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a.get(mid)<=x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return l;
				
	}
	public static long longest_Segment_sum_less_than_equal_to_S(long[] a,long sum,int n) {
		int l=0;
		long x=0;
		long res=0;
		for(int r=0;r<n;r++) {
			x+=a[r];
			while(x>sum) {
				x-=a[l];
			l++;
			}
			res=Math.max(r-l+1,res);
		}
		return res;
	}
	public static long shortest_Segment_sum_greater_than_equal_to_S(long[] a,long sum,int n) {
		int l=0;
		long x=0;
		long res=Integer.MAX_VALUE;
		for(int r=0;r<n;r++) {
			x+=a[r];
			while(x-a[l]>=sum) {
				x-=a[l];
				l++;
			}
			if(x>=sum) {
				res=Math.min(res, r-l+1);
			}
		}
		return res;
	}
	public static long total_Segment_sum_less_than_equal_to_S(long[] a,long sum,int n) {
	
		int l=0;
		long x=0;
		long res=0;
		for(int r=0;r<n;r++) {
			x+=a[r];
			while(x>sum) {
				x-=a[l];
				l++;
			}
			res+=((r-l+1));
		}
		return res;
	}
	public static long total_Segment_sum_greater_than_equal_to_S(long[] a,long sum,int n) {
		
		int l=0;
		int l1=-1;
		int r1=-1;
		long x=0;
		long res=0;
		for(int r=0;r<n;r++) {
			x+=a[r];
			while(x-a[l]>=sum) {
				x-=a[l];
				l++;
			}
			if(x>=sum && l!=l1 && r!=r1) {
				res+=(long)(l-l1)*(n-r);
				l1=l;
//				System.out.println(l+" "+l1+" "+r+" "+r1);
			}
			r1=r;
		}
		return res;
	}
	public static long total_Segment_unique_elements_less_than_equal_to_S(long[] a,long k,int n) {
		int l=0;
//		int r=0;
		int count=0;
		long res=0;
		int[] ct=new int[100001];
		for(int r=0;r<n;r++) {
			ct[(int) a[r]]++;
			if(ct[(int) a[r]]==1) {
				count++;
			}
				while(count>k) {
					ct[(int) a[l]]--;
					if(ct[(int) a[l]]==0) {
						count--;
					}
					l++;
				}
				res+=(r-l+1);
			
		}
		return res;
		
	}
	public static long segment_with_maximum_spread(long[] a,int n,long k)
	{
		int l=0;
		long count=0;
	for(int r=0;r<n;r++) {
		add(a[r]);
		while(!good(k)) {
			remove();
			l++;
		}
		count+=r-l+1;
//		System.out.println(r+" "+l);
	}
		return count;
	}
	
public static class Stack1{
	
	private  Stack<Long> st;
	private  Stack<Long> smin;
	private  Stack<Long> smax;
Stack1(){
	this.st=new Stack<>();
	this.smin=new Stack<>();
	this.smax=new Stack<>();
	this.smin.add(Long.MAX_VALUE);
	this.smax.add(Long.MIN_VALUE);
}	 
	
}
static Stack1 st1=new Stack1();
static Stack1 st2=new Stack1();
static void add(long d) {
	st2.st.add(d);
	st2.smin.add(Math.min(d, st2.smin.peek()));
	st2.smax.add(Math.max(st2.smax.peek(),d));
}
static void remove() {
	if(st1.st.isEmpty()) {
		while(!st2.st.isEmpty()) {
			st1.st.add(st2.st.pop());
			st2.smin.pop();
			st2.smax.pop();
			st1.smax.add(Math.max(st1.smax.peek(), st1.st.peek()));
			st1.smin.add(Math.min(st1.smin.peek(), st1.st.peek()));
		}}
		st1.st.pop();
		st1.smax.pop();
		st1.smin.pop();
	
}
static boolean good(long k) {
	long min=Math.min(st1.smin.peek(), st2.smin.peek());
	long max=Math.max(st1.smax.peek(), st2.smax.peek());
	return max-min<=k;
}



public static class Stack2{
	
	private  Stack<Long> st;
	private  Stack<Long> gcd;
Stack2(){
	this.st=new Stack<>();
	this.gcd=new Stack<>();
	gcd.add((long) 0);
}	 
	
}
static Stack2 st3=new Stack2();
static Stack2 st4=new Stack2();
static void add2(long d) {
	st4.st.add(d);
	st4.gcd.add(GCD(st4.gcd.peek(),d));
}
static void remove2() {
	if(st3.st.isEmpty()) {
		while(!st4.st.isEmpty()) {
			st3.st.add(st4.st.pop());
			st4.gcd.pop();
			st3.gcd.add(GCD(st3.gcd.peek(),st3.st.peek()));
			
		}}
		st3.st.pop();
		st3.gcd.pop();
	
}
static boolean good2() {
	if(st3.st.isEmpty()) {
		while(!st4.st.isEmpty()) {
			st3.st.add(st4.st.pop());
			st4.gcd.pop();
			st3.gcd.add(GCD(st3.gcd.peek(),st3.st.peek()));
			
		}}
	long d=st3.gcd.pop();
	long g=st3.gcd.peek();
	st3.gcd.add(d);
	return GCD(g,st4.gcd.peek())==1;
}


public static long GCD(long a,long b) {
	if(b==(long)0) {
		return a;
	}
	return GCD(b , a%b);
}
public static boolean good3() {
	return GCD(st3.gcd.peek(),st4.gcd.peek())==1;
}
public static long shortest_Segment_gcd_equal_to_one(long[] a,int n) {
	int l=0;
	long x=0;
	long res=Integer.MAX_VALUE;
	for(int r=0;r<n;r++) {
		add2(a[r]);
		while(good2()) {
		remove2();
			l++;
		}
		if(good3()) {
			res=Math.min(res, r-l+1);
		}
	}
	return res;
}
public static long[] merge_sort(long[] A, int start, int end) {
	if (end > start) {
		int mid = (end + start) / 2;
		long[] v = merge_sort(A, start, mid);
		long[] o = merge_sort(A, mid + 1, end);
		return (merge(v, o));
	} else {
		long[] y = new long[1];
		y[0] = A[start];
		return y;
	}
}
public static long[] merge(long a[], long b[]) {
//	int count=0;
	long[] temp = new long[a.length + b.length];
	int m = a.length;
	int n = b.length;
	int i = 0;
	int j = 0;
	int c = 0;
	while (i < m && j < n) {
		if (a[i] < b[j]) {
			temp[c++] = a[i++];
		
		} else {
			temp[c++] = b[j++];
		}
	}
	while (i < m) {
		temp[c++] = a[i++];
	}
	while (j < n) {
		temp[c++] = b[j++];
	}
	return temp;
}
//public static pair2[] merge_sort(pair2[] A, int start, int end) {
//	if (end > start) {
//		int mid = (end + start) / 2;
//		pair2[] v = merge_sort(A, start, mid);
//		pair2[] o = merge_sort(A, mid + 1, end);
//		return (merge(v, o));
//	} else {
//		pair2[] y = new pair2[1];
//		y[0] = A[start];
//		return y;
//	}
//}
//public static pair2[] merge(pair2 a[], pair2 b[]) {
////	int count=0;
//	pair2[] temp = new pair2[a.length + b.length];
//	int m = a.length;
//	int n = b.length;
//	int i = 0;
//	int j = 0;
//	int c = 0;
//	while (i < m && j < n) {
//		if (a[i].a > b[j].a) {
//			temp[c++] = a[i++];
//		
//		}else if(a[i].a==b[j].a) {
//			if(Math.abs(a[i].c-a[i].b)<Math.abs(b[j].b-b[j].c)) {
//				temp[c++]=a[i++];
//				}else if(Math.abs(a[i].c-a[i].b)==Math.abs(b[j].b-b[j].c)) {
//					if(a[i].c>b[j].c) {
//						temp[c++]=a[i++];
//					}else {
//						temp[c++]=b[j++];
//					}
//				}
//			
//			else {
//					temp[c++]=b[j++];
//				}
//		}
//		else {
//			temp[c++] = b[j++];
//		}
//	}
//	while (i < m) {
//		temp[c++] = a[i++];
//	}
//	while (j < n) {
//		temp[c++] = b[j++];
//	}
//	return temp;
//}
}
