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.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main1 {
	static PrintWriter out = new PrintWriter(System.out);
	static FastReader input = new FastReader();
	static int n, a[], q, st[], lazy[];

	static void build(int i, int l, int r) {
		if (l == r) {
			st[i] = a[l];
		} else {
			build(i << 1, l, l + r >> 1);
			build((i << 1) + 1, (l + r >> 1) + 1, r);
			st[i] = Math.min(st[i << 1], st[(i << 1) + 1]);
		}
	}

	static void propagate(int i, int l, int r) {
		if (l != r) {
			lazy[i << 1] = Math.max(lazy[i], lazy[i << 1]);
			lazy[(i << 1) + 1] = Math.max(lazy[i], lazy[(i << 1) + 1]);
		}

		st[i] = Math.max(lazy[i], st[i]);
		lazy[i] = 0;

	}

	static void updateRange(int i, int l, int r, int x) {
		propagate(i, l, r);

		if (st[i] < x) {
			lazy[i] = Math.max(lazy[i], x);
			propagate(i, l, r);
		}
	}

	static int query(int i, int l, int r, int t) {
		propagate(i, l, r);
		if (l == r) {
			return st[i];
		} else if (t <= r + l >> 1) {
			return query(i << 1, l, r + l >> 1, t);
		} else {
			return query((i << 1) + 1, (l + r >> 1) + 1, r, t);
		}

	}

	static void updateSingle(int i, int l, int r, int t, int v) {
		propagate(i, l, r);

		if (l == r) {
			st[i] = v;
			return;
		} else if (t <= l + r >> 1) {
			updateSingle(i << 1, l, r + l >> 1, t, v);
		} else {
			updateSingle((i << 1) + 1, (l + r >> 1) + 1, r, t, v);
		}
		st[i] = Math.min(st[i << 1], st[(i << 1) + 1]);

	}

	static void print(int i, int l, int r) {
		propagate(i, l, r);
		if (l == r)
			out.print(st[i] + " ");
		else {
			print(i << 1, l, r + l >> 1);
			print((i << 1) + 1, (l + r >> 1) + 1, r);
		}
	}

	public static void main(String[] args) throws IOException {

		n = input.nextInt();
		a = new int[n];
		st = new int[n << 2];
		lazy = new int[n << 2];

		for (int i = 0; i < n; i++)
			a[i] = input.nextInt();
		build(1, 0, n - 1);
		q = input.nextInt();

		while (q-- > 0) {
			int f = input.nextInt();
			int p, x;
			if (f == 1) {
				p = input.nextInt();
				x = input.nextInt();
				updateSingle(1, 0, n - 1, (p - 1), x);

			} else {
				x = input.nextInt();
				updateRange(1, 0, n - 1, x);

			}

		}
		print(1, 0, n - 1);

		out.flush();
	}

	static class con {
		static int IINF = (int) 1e9;
		static int _IINF = (int) -1e9;
		static long LINF = (long) 1e15;
		static long _LINF = (long) -1e15;
		static double EPS = 1e-9;
	}

	static class Triple implements Comparable<Triple> {
		int x;
		int y;

		int z;

		Triple(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

		@Override
		public int compareTo(Triple o) {
			if (x == o.x && y == o.y)
				return z - o.z;
			if (x == o.x)
				return y - o.y;
			return x - o.x;
		}

		@Override
		public String toString() { return "(" + x + ", " + y + ", " + z + ")"; }
	}

	static class Pair implements Comparable<Pair> {
		int x;
		int y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;

		}

		@Override
		public int compareTo(Pair o) {
			if (x == o.x)
				return y - o.y;
			return x - o.x;
		}

		@Override
		public String toString() {

			return "(" + x + ", " + y + ")";
		}

	}

	static void shuffle(int[] a) {
		for (int i = 0; i < a.length; i++) {
			int r = i + (int) (Math.random() * (a.length - i));
			int tmp = a[r];
			a[r] = a[i];
			a[i] = tmp;
		}
	}

	static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

	static class DSU {

		int[] p, rank, setSize;
		int numSets;

		DSU(int n) {
			p = new int[n];
			rank = new int[n];
			setSize = new int[n];
			numSets = n;

			for (int i = 0; i < n; i++) {
				p[i] = i;
				setSize[i] = 1;
			}

		}

		int findSet(int n) { return p[n] = p[n] == n ? n : findSet(p[n]); }

		boolean isSameSet(int n, int m) { return findSet(n) == findSet(m); }

		void mergeSet(int n, int m) {

			if (!isSameSet(n, m)) {
				numSets--;
				int p1 = findSet(n);
				int p2 = findSet(m);

				if (rank[p1] > rank[p2]) {
					p[p2] = p1;
					setSize[p1] += setSize[p2];
				} else {
					p[p1] = p2;
					setSize[p2] += setSize[p1];
					if (rank[p1] == rank[p2])
						rank[p1]++;
				}
			}

		}

		int size() { return numSets; }

		int setSize(int n) { return setSize[findSet(n)]; }

	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); }

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

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

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

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

		String nextLine() throws IOException {
			String str = "";
			str = br.readLine();
			return str;
		}

		boolean hasNext() throws IOException { return br.ready(); }
	}
}