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.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main
{
	static class Tree
	{
		long sum;
		
		public Tree()
		{
			this.sum=0;
		}	
		public Tree(long val)
		{
		   this.sum=val;
		}	
		public void setval(long val)
		{
			this.sum=val;
		}
		public void merge(Tree left,Tree right)
		{
			this.sum=Math.max(left.sum,right.sum);		
		}	
	}
	
   static long mod=(long)(1e+9 + 7);
   //static long mod=(long)998244353;
   
   static int[] sieve;
   static ArrayList<Integer> primes;
   static long min=Long.MAX_VALUE;
   
   static int a[];
   static Tree[] tree;    
   static Tree[] lazy; 
   static int MAXN;
   static PrintWriter out;
     	

  public static void lazy(int n,int start,int end)
  {
      if(lazy[n].sum!=0)
	   {
		   tree[n].sum=Math.max(tree[n].sum,lazy[n].sum);
		   if(start!=end)
		   {
		   lazy[n<<1].sum=Math.max(lazy[n<<1].sum,lazy[n].sum);
		   lazy[(n<<1) + 1].sum=Math.max(lazy[(n<<1)+1].sum,lazy[n].sum);
		   }
		   lazy[n].sum=0;
	   }
  }
  

  public static void build(int n,int start,int end,int size)
  {
	   int mid=(start+end)>>1;
	   
	   if(start==end && start>size) 
	   {
		   tree[n]=new Tree();
		   return;
	   }
	   if(start==end)
	   {
		   tree[n]=new Tree(a[start]);
		   return;
	   }
	   
	   build(n<<1,start,mid,size);
	   build((n<<1) + 1,mid+1,end,size);
	   
	   tree[n]=new Tree();
	   tree[n].merge(tree[n<<1], tree[(n<<1) + 1]);
  }
  
  public static Tree query(int n,int start,int end,int l ,int r)
  {
	   int mid=(start+end)>>1;
	   
	   lazy(n,start,end);
		
	   if(start>=l && end<=r) return tree[n];
	   else if(start > r || end<l) return null;
	   
	   Tree left=null, right=null;
	   
	   if(l<=mid) 
		   left=query(n<<1,start,mid,l,r);
	   if(r>mid)
		   right=query((n<<1) + 1,mid+1,end,l,r);
	   
	   if(left==null) return right;
	   if(right==null) return left;
	   
	   Tree t=new Tree();
	   t.merge(left, right);
	   
	   return t;
  }
  
  public static void pt_update(int n,int start,int end, int l,int r,long v)
	  {
		   int mid=(start+end)>>1;
		   
		   lazy(n,start,end);
		   if(start>r || end<l) {return;}	   
		   else if(start>=l && end<=r) 
		   {
			   tree[n].sum=v;
			   return;
		   }
		   else
		    {
			   pt_update((n<<1),start,mid,l,r,v) ;
			   pt_update((n<<1)+1,mid+1,end,l,r,v);
			   
		    }   
		   tree[n].merge(tree[n<<1],tree[(n<<1) + 1]);
	  }

  
   public static void main(String[] args) throws java.lang.Exception
   {	  	
	     fast s = new fast();
	     PrintWriter out=new PrintWriter(System.out);
	     
	     int t=1;
	     StringBuilder fans=new StringBuilder("");
	    
	     while(t>0)
	    	 {
	    		 int n=s.nextInt();
	    		 a=new int[n+1];
	    		
	    		MAXN = n;
	   		MAXN |= (MAXN >> 1);
	   		MAXN |= (MAXN >> 2);
	   		MAXN |= (MAXN >> 4);
	   		MAXN |= (MAXN >> 8);
	   		MAXN |= (MAXN >> 16);
	   		MAXN = MAXN + 1;
	   		
	   		tree = new Tree[2*MAXN+1];
	   		lazy = new Tree[2*MAXN+1];
	   		
	    		 for(int i=1;i<=n;i++) a[i]=s.nextInt();
	    		 
	    		for(int i=1;i<=2*MAXN;i++)
	       	   lazy[i]=new Tree();
	          
	          build(1,1,MAXN,n);
	          
	    		 int q=s.nextInt();
	    		
	    		 
	    		 for(int i=0;i<q;i++)
	    			 {
	    				 int qu=s.nextInt();
	    				 
	    				 if(qu==1)
	    					 {
	    						 int p=s.nextInt();
	    						 long x=s.nextLong();
	    						 
	    						 pt_update(1,1,MAXN,p,p,x);
	    					 }
	    				 else
	    					 {
	    						 long x=s.nextLong();
	    						 lazy[1].sum=Math.max(lazy[1].sum, x);
	    					 }
	    			 }
	    		 
	    		 int ans[]=new int[n+1];
	    		 
	    		 for(int i=1;i<=n;i++) 
	    			 {
	    				 ans[i]=(int)query(1,1,MAXN,i,i).sum;
	    				 fans.append(ans[i]+" ");
	    			 }
	    		 
	    		 System.out.println(fans);
	    		 t--;
	    	 }
   }
  
 
 
static class fast {   
	    private InputStream i;
		private byte[]  buf = new byte[1024];
		private int curChar;
		
		private int numChars;
		
		//Return floor log2n
		public static long log2(long bits) // returns 0 for bits=0
			{
			    int log = 0;
			    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
			    if( bits >= 256 ) { bits >>>= 8; log += 8; }
			    if( bits >= 16  ) { bits >>>= 4; log += 4; }
			    if( bits >= 4   ) { bits >>>= 2; log += 2; }
			    return log + ( bits >>> 1 );
			}
		
		public static boolean next_permutation(int a[])
		   {
			   int i=0,j=0;int index=-1;	   
			   int n=a.length;
			   
			   for(i=0;i<n-1;i++)
				   if(a[i]<a[i+1]) index=i;
			   
			   if(index==-1) return false;
			   i=index;
 
			  
			   for(j=i+1;j<n && a[i]<a[j];j++);
 
			   int temp=a[i];
			   a[i]=a[j-1];
			   a[j-1]=temp;
			   	   
			   for(int p=i+1,q=n-1;p<q;p++,q--)
			   {
				   temp=a[p];
				   a[p]=a[q];
				   a[q]=temp;
			   }
			   
			   return true;
		   }
		   
		   
		public static void division(char ch[],int divisor)
		   {
			   int div=Character.getNumericValue(ch[0]); int mul=10;int remainder=0;
			   StringBuilder quotient=new StringBuilder("");
			   for(int i=1;i<ch.length;i++)
			   {
				   div=div*mul+Character.getNumericValue(ch[i]);	
				   if(div<divisor) {quotient.append("0");continue;}
				   quotient.append(div/divisor);
				   div=div%divisor;mul=10;
				   
			   } 
			   remainder=div;
			   while(quotient.charAt(0)=='0')quotient.deleteCharAt(0);	   
			   System.out.println(quotient+" "+remainder);	  
		   }
		
		public static void sieve(int size)
		{
			sieve=new int[size+1];
			
			primes=new ArrayList<Integer>();
			
			sieve[1]=1;
			
			for(int i=2;i*i<=size;i++)
			{
				if(sieve[i]==0)
				 {
					for(int j=i*i;j<size;j+=i) {sieve[j]=1;}
				 }
			}
			
			for(int i=2;i<=size;i++)
			{
				if(sieve[i]==0) primes.add(i);
			}
		}
		
		public static long pow(long n, long b, long MOD)
		   {
		       long x=1;long y=n; 
		       while(b > 0)
		       {
		           if(b%2 == 1)
		           {
		               x=x*y;
		               if(x>MOD) x=x%(MOD);
		           }
		           y = y*y;
		           if(y>MOD) y=y%(MOD); 
		           b >>= 1;
		       }
		       return x;
		   }
 
 
		public static long mod_inv(long n,long mod)
		{
			return pow(n,mod-2,mod);
		}
		
		//Returns index of highest number less than or equal to key
		 public static int upper(long[] a,int length,long key)
		 {
			    int low = 0;
		        int high = length-1;
		        int ans=-1;
		        
		        while (low <= high) {
		            int mid = (low + high) / 2;
		            if (key >= a[mid]) {
		                ans=mid;
		            	low = mid+1;
		            } else if(a[mid]>key){
		                high = mid - 1;
		            }
		        }
		        return ans;
		}
		
		//Returns index of least number greater than or equal to key
		 public static int lower(long[] a,int length,long key)
		 {
			    int low = 0;
		        int high = length-1;
		        int ans=-1;
		        
		        while (low <= high) {
		            int mid = (low + high) / 2;
		            if (key<=a[mid]) {
		                ans=mid;
		            	high = mid-1;
		            }
		            else{
		            		low=mid+1;
		            	}
		        }
		        return ans;
		} 
		   
		public long gcd(long r,long ans)
		{
			if(r==0) return ans;
			return gcd(ans%r,r);
		}
		public fast() {
			this(System.in);
		}
		public fast(InputStream is) {
			i = is;
		}
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = i.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
		public String nextString() {
     		int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
 
	}	
}