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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

public class Main {
	
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
	

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

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

		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
    public static long mod = (long) (1e9+7);
    public final static int MAX = (int) 90000000;
   //Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
	   
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		int[] a = new int[n];
		TreeMap<Integer,Integer> map = new TreeMap<>();
		Map<Integer,Integer> freq = new HashMap<>();
		for(int i=0;i<n;++i) {
			a[i] = sc.nextInt();
		}
		int q = sc.nextInt();
		int[][] query = new int[q][3];
		int in = 0;
		while(q-->0) {
			int type = sc.nextInt();
			List<Integer> temp = new ArrayList<>();
			temp.add(type);
			query[in][0] = type;
			if(type == 1) {
				int p = sc.nextInt();
				int x = sc.nextInt();
				query[in][1] = p;
				query[in][2] = x;
			}else {
				int x = sc.nextInt();
				query[in][1] = x;
				map.put(x,in);
				add(freq,x);
			}
			++in;
			
		}
		
		int last = -1,start = 0;
		// main step
		for(int i=0;i<n && map.size()>0;++i) { 
			a[i] = Math.max(a[i],map.lastKey());
		}
		for(int key : map.descendingKeySet()) {
			 if(map.get(key)>last && freq.containsKey(key)) {
				last = map.get(key);
				 
				 for(int j=start;j<=last;++j) {
					  if(query[j][0] == 1) 
						  a[query[j][1]-1] = Math.max(query[j][2],key);
					  else {
						 delete(freq,query[j][1]);
					  }
				 }
				 start = last+1;
			 }
			
		}
		
		
		// remaining 1 query
		for(int i = start;i<query.length;++i) {
			if(query[i][0] == 1) a[query[i][1]-1] = query[i][2];
		}
		
		for(int x : a) out.print(x+" ");
		
		out.close();
		}
	
	
	private static void delete(Map<Integer, Integer> map, int i) {
		if(map.containsKey(i)) {
			if(map.get(i) == 1) map.remove(i);
			else map.put(i, map.get(i)-1);
		}
		
	}
	private static void add(Map<Integer, Integer> map, int i) {
		// TODO Auto-generated method stub
		if(map.containsKey(i)) map.put(i, map.get(i)+1);
		else map.put(i, 1);
		
	}
}