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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {

	static PrintWriter pw = new PrintWriter(System.out);
 static ArrayList<Integer>[] adjList;

	public static void main(String[] args) throws IOException, InterruptedException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n=Integer.parseInt(bf.readLine());
		int[] p=new int[n+1];
		st=new StringTokenizer(bf.readLine());
		for(int i=1;i<p.length;i++) 
			p[i]=Integer.parseInt(st.nextToken());
		int q= Integer.parseInt(bf.readLine());
		int[] maxQ=new int[q+1];
		int[] lastupdate=new int[n+1];
		for(int i=1;i<maxQ.length;i++) {
		st =new StringTokenizer(bf.readLine());
		int t=Integer.parseInt(st.nextToken());
		if(t==1) {
			int person=Integer.parseInt(st.nextToken());
			int x=Integer.parseInt(st.nextToken());
			p[person]=x;
			lastupdate[person]=i;
		}else {
			int c=Integer.parseInt(st.nextToken());
			maxQ[i]=c;
		}
			
		}
		for(int i=q-1;i>=0;i--)
			maxQ[i]=Math.max(maxQ[i], maxQ[i+1]);
		for(int i=1;i<=n;i++) {
			if(i!=n)
				pw.print(Math.max(p[i], maxQ[lastupdate[i]])+" ");
			else

				pw.println(Math.max(p[i], maxQ[lastupdate[i]]));
		}
		pw.flush();
		pw.close();

}
 public static void shuffle(int[] a)
	{
		int n = a.length;
		for(int i = 0; i < n; i++)
		{
			int r = i + (int)(Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}

public static double readDouble(String s) {
		StringBuilder sb =new StringBuilder("0");
		boolean neg=false;
		boolean dec=false;
		double div=1;
		int start=0;
		if(s.charAt(0)=='-') {
			neg=true;start++;
		}
		double result=0;
	for(int i=start;i<s.length();i++) {
		if(s.charAt(i)=='.') {
			result+=Long.parseLong(sb.toString());
	
			sb =new StringBuilder("0");
			dec=true;
		}else {
			sb.append(s.charAt(i));
			if(dec)
				div*=10;
		}
	}

	result+=Long.parseLong(sb.toString()) / div;
	return (neg)?-1*result:result;
}
public static int gcd(int a,int b) {
	if(a==0)return b;
	return gcd(b%a,a);
}
public static int pow(int a, int n) {
	int res=1;
	while(n>0) {
		if((n&1)==1)
			res*=a;
		a*=a;
		n>>=1;
	}
	return res;
}


//	public static boolean isPrimeNum(int n) {
//		if(n<isPrime.length)return isPrime[n];
//		int p=primes.get(0);
//		int idx=0;
//		while(p*p<=n) {
//			if(n%p==0)return false;
//		p=primes.get(++idx);
//		}
//		return true;
//	}
//
//	public static int binarySearch(int x) {
//		int start=0;
//		int end=arrSorted.length-1;
//		while(end-start+1>2) {
//			int mid =(start+end)>>1;
//			int midelem=arrSorted[mid];
//			if(arrSorted[mid-1]<=x&&midelem>x)return mid-1;
//			if(arrSorted[mid]==x)return mid;
//			if(midelem<x) start=mid;
//			else
//				end=mid;
//		}
//		if(arrSorted[end]<=x)return end;
//		return (arrSorted[start]<=x)?start:-1;
//	}
//public static int binarySearch(int x) {
//	int start=0;
//	int end=pf.length-1;
//	while(end-start+1>2) {
//		int mid =(start+end)>>1;
//		int midelem=pf[mid];
//		if(midelem==x)return mid;
//		if(midelem<x) start=mid;
//		else
//			end=mid;
//	}
//	if(pf[end]==x)return end;
//	if(pf[start]==x)return start;
//	return -1;
//
//}

	static boolean[] isPrime;
	static ArrayList<Integer> primes;
	static ArrayList<Integer>[] factors;//factors[i] if i=9 {3,2} 

	
public static void ModifiedSieveForFactors(int N) {// O( n log( log n ) )
		isPrime= new boolean[N+1];//u can save half the memory by neglecting all even numbers since they aren't primes
	primes= new ArrayList<>(N+1);
		Arrays.fill(isPrime, true);
		factors = new ArrayList[N+1];
		for(int i=0;i<=N;i++)
			factors[i]=new ArrayList<>();
		isPrime[0]=isPrime[1]=false;
		factors[1].add(2);
		factors[1].add(0);
		for(int i=2;i<=N;i++) {
			if(isPrime[i]) {
				for(int j=i;j<=N;j+=i) {
					isPrime[j]=false;
					int k=j;
					int count=0;
					while(k%i==0) {
						count++;
						k/=i;
					}
					factors[j].add(i);
					factors[j].add(count);
				}
				isPrime[i]=true;
			}
		}
		for(int i=0;i<isPrime.length;i++) {
			if(isPrime[i])primes.add(i);
		}
	}
public static int getPth(long M) {
	if(M<factors.length) {
		ArrayList<Integer>factor= factors[(int)M];
		int prev=factor.get(1);
		for(int i=3;i<factor.size();i+=2) {
			prev=gcd(prev,factor.get(i));
		}
		return prev;
	}else {
		int p=primes.get(0);
		int idx=0;
		boolean firstTime=true;
		int prev=1;
		while(p*1l*p<=M) {
			int count=0;
			boolean entered=false;
			while(M%p==0) {
				M/=p;
				count++;
				entered=true;
				
			}
			if(firstTime&&entered) {
				prev=count;
				firstTime=false;
			}else if(entered)prev=gcd(prev,count);
				
			p=primes.get(++idx);
			}
			
			if(M!=1)
				return 1;
			return prev;
	}
		
	}

	public static void sieve(int N) {// O( n log( log n ) )
		isPrime= new boolean[N+1];//u can save half the memory by neglecting all even numbers since they aren't primes
		primes= new ArrayList<>(N);
		Arrays.fill(isPrime, true);
		isPrime[0]=isPrime[1]=false;
		for(int i=2;i*i<=N;i++) {
			if(isPrime[i]) {
				for(int j=i*i;j<=N;j+=i) {
					isPrime[j]=false;
				}
			}
		}
		
		for(int i=2;i<=N;i++)
			if(isPrime[i])
				primes.add(i);
		
	}

	static long[] lcmCard;
	public static void LCMCard(int N) {//modified sieve
		lcmCard=new long[N+1];
		Arrays.fill(lcmCard,1);
		primes=new ArrayList<>();
		for(int i=2;i<=N;i++) {
			if(lcmCard[i]==1) {
				primes.add(i);
				for(int j =i;j<=N;j+=i) {
					int k=j;
					int count=0;
					while(k%i==0) {
						k/=i;
						count++;
					}
					lcmCard[j]*=((count<<1)+1);
				}
			}
		}
		
	}
	public static long findCard(int N) {
		if(N<lcmCard.length)return lcmCard[N];
		int p=primes.get(0);
		int idx=0;
		long r=1;
		while(p*p<=N) {
			int count=0;
			while(N%p==0) {
				N/=p;
				count++;
			}
			r*=((count<<1)+1);
			p=primes.get(++idx);
		}
		
		if(N!=1) {
			r*=3;
		}
		return r;
		
	}


	public static void addEdge(int a, int b) {
		adjList[a].add(b);
		adjList[b].add(a);
	}
	static class FenwickTree {//one-based DS
	//it's for reversable operations to be able to find a range but if u always want from 1 to j so it will work
	
int[] ft;// note it must be 1 based because ur first elem FT[1] is A[1 -LSON(1)]  (i'm kidding it can also be 0 based ) 
//to be consistent with segment tree let it to be 1 based
int n;

public FenwickTree(int n) {
	this.n=n;
	ft= new int[n+1];
}

public int LSONE(int i) {
	return i&(-i);
}

public void update_point(int  k ,int val) {//O(log n) because K will at worst case incremented with the number of ones in n so if to get number of bit
	// it's log(n)
	while(k<=n) {
		ft[k]+=val;
		k+=LSONE(k);
	}
}
public void update_range(int i , int j ,int val) {
	update_point(i, val);
	update_point(j+1, -val);//the inverse of the operation in our case it's subtraction
	
}
public int query(int k) {// we keep adding ft[k]+ft[k']+ft[k"]+... where k' =k-LSONE(K) till k==0 it's also O(log(n))
	int sum =0;
	while(k>0) {
		sum+=ft[k];
		k-=LSONE(k);
	}
	return sum;
}

public int query(int i , int j) {
	return query(j) - ((i<=1)?0:query(i-1));
}

public int pointQuery(int i) { //less than log n == no. of first zero bits till LSOne 
		int sum=ft[i];
		
		if(i>0) {
		//int z=(i)-(LSONE(i));	
			int z= i ^(i&-i); // turn off the LSONE
			i--;
		while(i!=z) {
			sum-=ft[i];
			i-=LSONE(i);
		}
		
		}
		return sum;
}



}


	
static public class SegmentTree {

		int N;
		int[] array;
		int[] lazy;
		int[] sTree;
		int[] idx;
//public node combine(node a,node b) {
//	int maxPos=Math.min(Math.abs(a.leftOpen),Math.abs( b.rightOpen));
//	return new node(a.leftOpen-maxPos+b.leftOpen,a.rightOpen+b.rightOpen-maxPos,a.sum+b.sum+maxPos);
//}
	
	public SegmentTree(int[] arr) {// note arr must be 1 based arr
			array = arr;
			N = arr.length - 1;// arr must be power of 2 and 1 based array
			sTree = new int[N << 1]; // no of nodes is 2N-1 but we add 1 to be 1 index
			lazy = new int[N << 1];
			idx=new int[N<<1];
			build(1, 1, N);

		}

	
	public void build(int v, int b, int e) {// o(N)
			if (b == e) {
				sTree[v] = array[b];
				idx[v]=b;
			} else {
				int mid = (b + e) >> 1;
				build((v << 1), b, mid);
				build((v << 1) | 1, mid + 1, e);
				sTree[v] =Math.max( sTree[v << 1] , sTree[(v << 1) | 1]);
				idx[v]=(sTree[v<<1|1]>=sTree[v<<1])?idx[v<<1|1]:idx[v<<1];
			}
		}

		public int query(int i, int j) {// O(2log(n))
			return query(1, 1, N, i, j);
		}

		public int getIdx(long max, int node) {
			int r = node;
			while (node < N - 1) {
				if (sTree[node << 1] == max)
					node <<= 1;
				else if (sTree[node << 1 | 1] == max)
					node = node << 1 | 1;
			}
			return node - (N - 1);
		}

		public int query(int node, int b, int e, int i, int j) {
			if (b > j || e < i)
				return 0;
			if (b >= i && e <= j) {
				return idx[node];

			}
			int mid = (b + e) >> 1;

			//propagate(node, b, mid, e);
			int leftChild = query(node << 1, b, mid, i, j);
			int rightChild = query((node << 1) | 1, mid + 1, e, i, j);

			return  array[rightChild]>=array[leftChild]?rightChild:leftChild;

		}

		public void set_point(int idx, int val) {

			idx += N - 1;
			sTree[idx] = val;
			boolean or = true;
			while (idx > 1) {
				idx >>= 1;
				sTree[idx] = sTree[idx << 1] + sTree[idx << 1 | 1];
			}
		}

		public void update_point(int idx, int val) {
			idx += N - 1;
			sTree[idx] += val;
			while (idx > 1) {
				idx >>= 1;// divide by 2 to get the parent
				sTree[idx] = sTree[(idx << 1)] + sTree[(idx << 1) | 1];
			}

		}

		public void update_range(int i, int j, int val) {
			update_range(1, 1, N, i, j, val);
		}

		public void update_range(int node, int b, int e, int i, int j, int val) {
			if (e < i || b > j)
				return;
			if (b >= i && e <= j) {
				sTree[node] += (e - b + 1) * val;
				lazy[node] += val;

			} else {

				int mid = (b + e) >> 1;
				propagate(node, b, mid, e);
				update_range(node << 1, b, mid, i, j, val);
				update_range(node << 1 | 1, mid + 1, e, i, j, val);
				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
			}
		}

		public void propagateAll() {
			propagateAll(1, 1, N);
		}

		public void propagateAll(int node, int b, int e) {

			if (b == e)
				return;
			int mid = (e + b) >> 1;
			propagate(node, b, mid, e);
			propagateAll(node << 1, b, mid);
			propagateAll((node << 1) | 1, mid + 1, e);

		}

		public void propagate(int node, int b, int mid, int e) { // O(1)
			if (lazy[node] == 0 || b == e)
				return;

			lazy[node << 1] += lazy[node];
			lazy[node << 1 | 1] += lazy[node];
			sTree[node << 1] += (mid - b + 1) * lazy[node];
			sTree[node << 1 | 1] += (e - mid) * lazy[node];
			sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];

			lazy[node] = 0;
		}

	}

	static public class UDS {
		int[] parent, rank, setSize;
		int n;// number of sets
		int maxSet = 1;

		public UDS(int n) {

			this.n = n;
			parent = new int[n];
			rank = new int[n];
			setSize = new int[n];
			Arrays.fill(setSize, 1);
			for (int i = 0; i < n; i++)
				parent[i] = i;
		}

		public boolean unionSet(int i, int j) {
			int p1 = findSet(i);
			int p2 = findSet(j);

			if (p1 != p2) {
				n--;
				if (rank[p1] < rank[p2]) {
					parent[p1] = p2;
					setSize[p2] += setSize[p1];
					maxSet = Math.max(maxSet, setSize[p2]);
				} else {
					parent[p2] = p1;
					setSize[p1] += setSize[p2];
					maxSet = Math.max(maxSet, setSize[p1]);
					if (rank[p1] == rank[p2])
						rank[p1]++;
				}
				return true;
			}
			return false;
		}

		public int sizeOfSet(int i) {
			return setSize[findSet(i)];
		}

		public int numDisjointSets() {
			return n;
		}

		public boolean isSameSet(int i, int j) {
			return findSet(i) == findSet(j);
		}

		public int findSet(int i) {
			return (parent[i] == i) ? i : (parent[i] = findSet(parent[i]));
		}
	}


}
