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.text.*;

public class D1199 {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		Stack<Triplet> st = new Stack<Triplet>();
		int n = sc.nextInt();
		int[] arr = new int[n];
		int idx =0;
		int m =n;
		while (m-- > 0) {
			st.add(new Triplet(1,idx++,sc.nextInt()));
		}
		int q = sc.nextInt();
		
		
		
		
		while (q-- > 0) {
			int e = sc.nextInt();
			int h = -1;
			int u = -1;
			if (e == 1) {
				h = sc.nextInt() - 1;
				u = sc.nextInt();
			} else
				h = sc.nextInt();
			st.add(new Triplet(e, h, u));
		}
		boolean[] changed = new boolean[n];
		int min = -1;
		while (!st.isEmpty()) {
			Triplet t = st.pop();
			if (t.x == 1) {
				int x = t.y;
				int p = t.z;
				if (changed[x])
					continue;
				if (p > min) {
					arr[x] = p;
					changed[x] = true;
				} else
				{
					arr[x] = min;
					changed[x] =true;
				}
			} else {
				min = Math.max(min, t.y);
			}
		}
//		pw.println(Arrays.toString(arr));
		for (int i = 0; i < arr.length; i++) {
			pw.print( arr[i]+ " ");
		}
		pw.close();

	}

	static class Triplet {
		int x, y, z;

		public Triplet(int a, int b, int c) {
			x = a;
			y = b;
			z = c;
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader r) {
			br = new BufferedReader(r);
		}

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

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

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

	}
}
