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.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	static StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pr = new PrintWriter(new BufferedOutputStream(System.out));
	static Scanner sc = new Scanner(System.in);

//		long tic = System.currentTimeMillis();
//		long toc = System.currentTimeMillis();
//		System.out.println("Elapsed time: " + (toc - tic) + " ms");
	public static void main(String[] args) {
		int n = nextInt();
		int aa[] = new int[n + 5];
		for (int i = 1; i <= n; ++i) {
			aa[i] = nextInt();
		}
		int q = nextInt();
		int bb[] = new int[q + 5];
		int cc[] = new int[q + 5];
		ArrayList<Node> vec = new ArrayList<>();
		for (int i = 1; i <= q; i++) {
			int op = nextInt();
			if (op == 1) {
				int p = nextInt();
				int x = nextInt();
				vec.add(new Node(i, p, x));
			} else {
				bb[i] = nextInt();
			}
		}
		for (int i = q; i > 0; i--) {
			cc[i] = Math.max(cc[i + 1], bb[i]);
		}
		for (int i = 1; i <= n; i++)
			aa[i] = Math.max(cc[1], aa[i]);
		for (Node it : vec) {
			aa[it.b] = Math.max(it.c, cc[it.a]);
		}
		for (int i = 1; i <= n; i++) {
			pr.print(aa[i] + " ");
		}
		pr.flush();
	}

	static int nextNum() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int) st.nval;
	}

	static int log2(long x) {
		int flag = 1;
		int log = 0;
		while (x > flag) {
			flag <<= 1;
			log++;
		}
		return log;
	}

	static long phi(int x) {
		long res = x;
		for (long i = 2; i <= Math.sqrt(x); i++) {
			if (x % i == 0) {
				while (x % i == 0)
					x /= i;
				res = res / i * (i - 1);
			}
		}
		if (x > 1)
			res = res / x * (x - 1);
		return res;
	}

	static long pow(long a, long b, long mod) {
		if (b == 0)
			return 1;
		if (b == 1)
			return a;
		if ((b & 1) == 0)
			return pow(a * a % mod, b >> 1, mod);
		else
			return a * pow(a * a % mod, b >> 1, mod) % mod;
	}

	static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		} else {
			return gcd(b, a % b);
		}
	}

	static int nextInt() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int) st.nval;
	}

	static double nextDouble() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return st.nval;
	}

	static String next() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return st.sval;
	}

	static long nextLong() {
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (long) st.nval;
	}
}

class Node {
	int a;
	int b;
	int c;

	public Node() {
	}

	public Node(int a, int b, int c) {
		super();
		this.a = a;
		this.b = b;
		this.c = c;
	}

	@Override
	public String toString() {
		return "Node [a=" + a + ", b=" + b + "]";
	}
}