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.*;
import java.util.*;
public class Problem7 {
	static Scanner sc=new Scanner(System.in);
	static PrintWriter out=new PrintWriter(System.out);
	public static void main(String[] args) throws IOException {
		int n=sc.nextInt();
		int N=1;
		while(n>N) {
			N=N<<1;
		}
		int a[]=new int[N+1];
		for (int i = 1; i <=n; i++) {
			a[i]=sc.nextInt();
			
		}
		int q=sc.nextInt();
	SegmentTree st=new SegmentTree(a);
	while(q-->0){
		int p=sc.nextInt();
		if(p==1) {
			int idx=sc.nextInt();
			int v=sc.nextInt();
			st.update_range(idx, idx, v, false);;
		}
		else if(p==2) {
		st.update_range(0, n, sc.nextInt(),true);	
		}
		
	}
	for (int i = 1; i <=n; i++) {
		System.out.println(st.query(i, i));
	}
	
	
	}


	 static class Scanner {
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s) {
		br = new BufferedReader(new InputStreamReader(s));
	}

	public String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	public int[] nextIntArr(int n) throws IOException {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextInt();
		return arr;
	}

	public long[] nextLongArr(int n) throws IOException {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextLong();
		return arr;
	}

	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	public String nextLine() throws IOException {
		return br.readLine();
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	public boolean ready() throws IOException {
		return br.ready();
	}
	public void waitForInput() throws InterruptedException {Thread.sleep(1000);}
}



 static class SegmentTree {
	int N; // number of elements in my array after the padding
	int [] array, sTree, lazy; 
	SegmentTree(int []inp){
	
		N=inp.length-1;
		array = inp;
		sTree =  new int[N<<1];
		lazy =  new int[N<<1];
		build(1, 1, N);
	}
	void build(int node, int b, int e) {
		if(b == e) {
			//node = b + N - 1
			// update(idx , value)
			// sTree[idx + N - 1] += value
			sTree[node] = array[b];
		}
		else {
			int nodeLeft = node << 1;
			int nodeRight = (node << 1)+1;
			int mid = (b + e) >> 1;
			build(nodeLeft, b , mid);
			build(nodeRight, mid + 1, e);
			sTree[node] = Math.max(sTree[nodeLeft] , sTree[nodeRight]);
		}
	}
	void propagate(int node, int b, int e) {
		int leftChild = node << 1;
		int rightChild = node<<1|1;
		lazy[leftChild] = Math.max(lazy[node],lazy[leftChild]);
		lazy[rightChild] = Math.max(lazy[node],lazy[rightChild]);
		int mid = (b + e)>>1;
		sTree[leftChild] = Math.max(sTree[leftChild],lazy[node]);
		sTree[rightChild] =Math.max(sTree[rightChild],lazy[node]);
		lazy[node] = 0;
	}
	// add value v for element in position idx in my input array
	//O(log(N))
	void update_point(int idx, int v) {
		int node = idx + N - 1;
		sTree[node] = v;
		while(node > 1) {
			node >>= 1;
			sTree[node] = Math.max(sTree[node << 1] , sTree[node << 1 | 1]);
		}
	}
	// O(log(N))
	int query(int i, int j) {
		return query(1, 1, N, i); 
	}
	int query(int node, int b, int e, int i)	// O(log n)
	{
		if(i>e || i<b)
			return 0;		
		if(b>= i && e <= i)
			return sTree[node];
		int mid = b + e >> 1;
		propagate(node, b,  e);
		int q1 = query(node<<1,b,mid,i);
		int q2 = query(node<<1|1,mid+1,e,i);
		return Math.max(q1,q2);	
				
	}
	void update_range(int i, int j, int val,boolean m) { //O(log(N))
		update_range(1, 1, N, i, j, val,m); 
	}
	void update_range(int node, int b, int e, int i, int j, int val,boolean modified) {
		if(i > e || j < b)
			return;
		if(b >= i && e <= j) {
			if(modified) {
			sTree[node] = Math.max(val, sTree[node]);
			lazy[node] =Math.max(lazy[node], val);
			}
			else {
				sTree[node]=val;
				lazy[node]=0;
			}
			
		}
		else {
			int mid = (b + e) >> 1;
			propagate(node, b, e);
			update_range(node<<1, b , mid, i, j, val,modified);
			update_range(node<<1|1, mid+1, e, i, j, val,modified);
			sTree[node] = Math.max(sTree[node<<1] , sTree[node<<1|1]);
		}
	}

 }
}
