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

public class Main {

	static final int MAX_N = 1000010;
	static final int INF = 0x3f3f3f3f;
	static final int mod = 1000000007;


	public static void main(String[] args) throws IOException {
		initReader(System.in);

		// int T = nextInt();
		// for (int i = 1; i <= T; i++)
			solve();

		pw.flush();
	}


	/*******************************************************************************************************************************/

	static int[] a;
	static Node[] C;

	public static void solve() throws IOException {
		int n = nextInt();

		a = new int[n + 1];
		C = new Node[n << 2];

		for (int i = 1; i <= n; i++) {
			a[i] = nextInt();
		}

		build(1, n, 1);

		int q = nextInt();

		while (q-- > 0) {
			int op = nextInt();

			if (op == 1) {
				int p = nextInt();
				int x = nextInt();

				update(p, x, 1, n, 1);
			} else {
				int x = nextInt();

				update(x, 1, n, 1, n, 1);
			}
		}

		for (int i = 1; i <= n; i++) {
			pw.print(query(i, 1, n, 1) + " ");
		}

		pw.println();
	}

	public static void pushUp(int root) {
		C[root].value = Math.min(C[root << 1].value, C[root << 1 | 1].value);
	}

	public static void pushDown(int root) {
		if (C[root].have) {
			Node left = C[root << 1];
			Node right = C[root << 1 | 1];

			if (!left.have || left.lazy < C[root].lazy) {
				left.lazy = C[root].lazy;
				left.have = true;
			}

			if (left.value < left.lazy) {
				left.value = left.lazy;
			}

			if (!right.have || right.lazy < C[root].lazy) {
				right.lazy = C[root].lazy;
				right.have = true;
			}

			if (right.value < right.lazy) {
				right.value = right.lazy;
			}

			C[root].have = false;
			C[root].lazy = 0;
		}
	}

	public static void build(int l, int r, int root) {
		C[root] = new Node(0, 0, false);

		if (l == r) {
			C[root].value = a[l];
			return;
		}

		int mid = l + r >> 1;
		build(l, mid, root << 1);
		build(mid + 1, r, root << 1 | 1);

		pushUp(root);
	}

	public static void update(int k, int v, int l, int r, int root) {
		if (l == r) {
			C[root].value = v;
			C[root].have = false;
			C[root].lazy = 0;
			return;
		}

		pushDown(root);

		int mid = l + r >> 1;
		if (k <= mid) {
			update(k, v, l, mid, root << 1);
		} else {
			update(k, v, mid + 1, r, root << 1 | 1);
		}

		pushUp(root);
	}

	public static void update(int v, int L, int R, int l, int r, int root) {
		if (L <= l && r <= R) {
			if (C[root].value < v) {
				C[root].value = v;
				C[root].lazy = v;
				C[root].have = true;
			}
			return;
		}

		pushDown(root);

		int mid = l + r >> 1;
		if (L <= mid) {
			update(v, L, R, l, mid, root << 1 | 1);
		}

		if (R > mid) {
			update(v, R, L, mid + 1, r, root << 1 | 1);
		}

		pushUp(root);
	}

	public static int query(int k, int l, int r, int root) {
		if (l == r) {
			return C[root].value;
		}

		pushDown(root);

		int mid = l + r >> 1;
		if (k <= mid) {
			return query(k, l, mid, root << 1);
		} else {
			return query(k, mid + 1, r, root << 1 | 1);
		}
	}


	/*******************************************************************************************************************************/

	static BufferedReader reader;
	static StringTokenizer tokenizer;
	static PrintWriter pw;

	public static void initReader(InputStream input) throws IOException {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
		pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

//		reader = new BufferedReader(new FileReader("ate.in"));
//		tokenizer = new StringTokenizer("");
//		printWriter = new PrintWriter(new BufferedWriter(new FileWriter("ate.out")));
	}

	public static boolean hasNext() {
		try {
			while (!tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
		} catch (Exception e) {
			return false;
		}
		return true;
	}

	public static String next() throws IOException {
		while (!tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}

	public static String nextLine() {
		try {
			return reader.readLine();
		} catch (Exception e) {
			return null;
		}
	}

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

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

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

	public static char nextChar() throws IOException {
		return next().charAt(0);
	}

	static class Node {
		int value;
		int lazy;
		boolean have;

		public Node(int value, int lazy, boolean have) {
			// TODO Auto-generated constructor stub

			this.value = value;
			this.lazy = lazy;
			this.have = have;
		}
	}
}
