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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Set;
import java.util.StringTokenizer;

public class TaskD {
	public static void main(String[] arg) {
		final FastScanner in = new FastScanner(System.in);
		final PrintWriter out = new PrintWriter(System.out);
		final int n = in.nextInt();
		final int[][] a = new int[n][2];// store processed result
		for (int i = 0; i < n; i++) {
			a[i][0] = in.nextInt();
			a[i][1] = 0;// not processed
		}
		final int q = in.nextInt();
		final int[][] act = new int[q][3];
		for (int i = 0; i < q; i++) {
			act[i][0] = in.nextInt();
			act[i][1] = in.nextInt();
			if (act[i][0] == 1) {
				act[i][1]--;
				act[i][2] = in.nextInt();
			}
		}

		int[] segTree = buildST(q, act);
		for (int i = act.length - 1; i >= 0; i--) {
			if (act[i][0] == 1 && a[act[i][1]][1] == 0) {
				a[act[i][1]][1] = 1;// mark as processed
				a[act[i][1]][0] = Math.max(act[i][2], query(segTree, i, act.length));
			}
		}

		final int max = query(segTree, 0, q);
		final StringBuilder sb = new StringBuilder();
		for (int i = 0; i < a.length; i++) {
			if (a[i][1] == 0 && a[i][0] < max) {
				a[i][0] = max;
			}
			sb.append(a[i][0]).append(' ');
		}
		out.println(sb.toString());
		out.close();
		in.close();
	}

	public static int[] buildST(final int q, final int[][] act) {
		final int[] segTree = new int[2 * q];// may be 4

		for (int i = q; i < segTree.length; i++) {
			if (act[i - q][0] == 2) {
				segTree[i] = act[i - q][1];
			}
		}

		for (int i = q - 1; i > 0; i--) {
			segTree[i] = Math.max(segTree[i << 1], segTree[i << 1 | 1]);
		}

		return segTree;
	}

	private static int query(int segTree[], int l, int r) {
		int res = 0;
		int n = segTree.length >> 1;

		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if ((l & 1) > 0)
				res = Math.max(res, segTree[l++]);

			if ((r & 1) > 0)
				res = Math.max(segTree[--r], res);
		}

		return res;
	}

	private static class Solution {

	}

	public static int log2(int n) {
		if (n <= 0)
			throw new IllegalArgumentException();
		return 31 - Integer.numberOfLeadingZeros(n);
	}

	private static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		FastScanner(InputStream stream) {
			try {
				br = new BufferedReader(new InputStreamReader(stream));
			} catch (Exception e) {
				e.printStackTrace();
			}
		}

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

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

		int[] readIntArr(int n) {
			int[] result = new int[n];
			for (int i = 0; i < n; i++) {
				result[i] = Integer.parseInt(next());
			}
			return result;
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}

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

	}

}
