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.io.*;
import java.math.*;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;

public class Solution {
	
	static class Pair {
		int index, val;
		Pair(int x, int y) {
			this.index = x;
			this.val = y;
		}
	}

	//SOLUTION BEGIN
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();// FAST INPUTS
		int n = sc.nextInt();
		int arr[] = sc.readArray(n);
		int q = sc.nextInt();
		int dp[] = new int[q];
		Arrays.fill(dp,-1);
		HashMap<Integer, Pair> map = new HashMap<Integer, Pair>();
		for(int i = 0; i<q; i++) {
			int t = sc.nextInt();
			if(t == 1) {
				int index =sc.nextInt()-1,val = sc.nextInt();
				map.put(index, new Pair(i, val));
			}
			else {
				int x = sc.nextInt();
				dp[i] = x;
			}
		}
		for(int i = q-2; i>=0; i--) {
			dp[i] = max(dp[i], dp[i+1]);
		}
		for(int i = 0; i<n; i++) {
			if(map.containsKey(i)) {
				arr[i] = map.get(i).val;
				arr[i] = max(arr[i], dp[map.get(i).index]);
			}
			else {
				arr[i] = max(arr[i], dp[0]);
			}
			
		}
		for(int e : arr)System.out.print(e+" ");
		
	}
	
	//SOLUTION END

	
	
	static void sort(int[] a) {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

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

		int[] readArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

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

}
