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
/*input
 
5
3 50 2 1 10
3
1 2 0
2 8
1 3 20





*/
import java.io.*;
import java.util.*;

 
public class mymy
{
 
	static OutputStream outputStream = System.out;
	static PrintWriter out = new PrintWriter(outputStream);
	static InputStream inputStream = System.in;
	static InputReader br = new InputReader(inputStream);

	static int n;
	static int[] a;

	static class node implements Comparable<node>
	{
		int data;int indx;
	
		node(int i,int o)
		{
			data=i;indx=o;
		}
		public int compareTo(node n)
		{
			if(this.data!=n.data) return this.data-n.data;
			return this.indx-n.indx;
		}
	}
	

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

		n=br.nextInt();
		a=new int[n];

		for(int i=0;i<n;i++) a[i]=br.nextInt();


		TreeSet<node> tr=new TreeSet<node>();


		int max2=0;


		ArrayList<Integer> qw=new ArrayList<Integer>();
		ArrayList<Integer> qp=new ArrayList<Integer>();
		ArrayList<Integer> qx=new ArrayList<Integer>();

		int q=br.nextInt();


		for(int i=0;i<q;i++)
		{
			int wht=br.nextInt();

			if(wht==1)
			{
				qw.add(1);
				qp.add(br.nextInt()-1);
				qx.add(br.nextInt());
			}
			else
			{
				int xx=0;
				qw.add(2);
				qp.add(-1);
				qx.add(xx=br.nextInt());
				max2=Math.max(max2,xx);
				tr.add(new node(xx,i));
			}
		}

		for(int i=0;i<n;i++) a[i]=Math.max(a[i],max2);



		for(int i=0;i<q;i++)
		{
			if(qw.get(i)==1)
			{
				node last=null;
				if(tr.size()>0) last=tr.pollLast();

				a[qp.get(i)]=qx.get(i);

				if(last!=null) a[qp.get(i)]=Math.max(a[qp.get(i)],last.data);

				if(last!=null) tr.add(last);

			}
			else
			{
				tr.remove(new node(qx.get(i),i));
			}

		}

		for(int i=0;i<n;i++) out.print(a[i]+" ");

		out.println();

		
		
 
		out.close();
 
	}





















	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
 
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
 
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
 
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
 
	}
	
}