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.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static int n,q;
	static final int maxn=(int) (2e5+10);
	static class tree{
		int l,r,min,lazy;
	}
	static tree tr[]=new tree[maxn<<2];
	static void build(int l,int r,int rt){
		tr[rt].l=l;
		tr[rt].r=r;
		if(l==r){
			tr[rt].min=nextInt();
			return;
		}
		int mid=(l+r)/2;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
		tr[rt].min=Math.min(tr[rt<<1].min, tr[rt<<1|1].min);
	}
	static void down(int rt){
		if(tr[rt].lazy!=0){
			tr[rt<<1].lazy=Math.max(tr[rt].lazy, tr[rt<<1].lazy);
			tr[rt<<1|1].lazy=Math.max(tr[rt].lazy, tr[rt<<1|1].lazy);
			tr[rt<<1].min=Math.max(tr[rt].lazy, tr[rt<<1].min);
			tr[rt<<1|1].min=Math.max(tr[rt].lazy, tr[rt<<1|1].min);
			tr[rt].lazy=0;
		}
	}
	static void update(int p,int x,int rt){//区间点修改
		if(tr[rt].l==tr[rt].r){
			tr[rt].min=x;
			return;
		}
		down(rt);
		int mid=(tr[rt].l+tr[rt].r)/2;
		if(p<=mid)
			update(p, x, rt<<1);
		else
			update(p, x, rt<<1|1);
		tr[rt].min=Math.min(tr[rt<<1].min, tr[rt<<1|1].min);
	}
	static void update(int x,int rt){//小于x都修改
		if(tr[rt].min>=x)
			return;
		tr[rt].min=x;
		tr[rt].lazy=Math.max(tr[rt].lazy, x);
	}
	static int query(int x,int rt){
		if(tr[rt].l==tr[rt].r)
			return tr[rt].min;
		down(rt);
		int mid=(tr[rt].l+tr[rt].r)/2;
		if(x<=mid)
			return query(x,rt<<1);
		return query(x, rt<<1|1);
	}
	static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	public static void main(String[] args) {
		PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
		n=nextInt();
		for(int i=0;i<4*n+5;i++){
			tr[i]=new tree();
		}
		build(1,n,1);
		q=nextInt();
		while(q-->0){
			int opt=nextInt();
			if(opt==1){
				int a,b;
				a=nextInt();
				b=nextInt();
				update(a,b,1);
			}else if(opt==2){
				int a=nextInt();
				update(a, 1);
			}
		}
		for(int i=1;i<=n;i++){
			out.print(query(i,1)+" ");
		}
		out.flush();
	}
	static int nextInt(){
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int)st.nval;
	}
}
