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
/*
this might be bustin bhoi
*/
import java.util.*;
import java.io.*;

   public class D2
   {
      public static void main(String args[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         int Q = Integer.parseInt(infile.readLine());
         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
         int[] track = new int[N];
         Arrays.fill(track, -1);
         for(int i=0; i < Q; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int tag = Integer.parseInt(st.nextToken());
            if(tag == 1)
            {
               int dex = Integer.parseInt(st.nextToken());
               int v = Integer.parseInt(st.nextToken());
               arr[dex-1] = v;
               track[dex-1] = i;
            }
            else
            {
               int boof = Integer.parseInt(st.nextToken());
               map.put(i, boof);
            }
         }
         //lmao 
         RangeTree rmq = new RangeTree(Q+1);
         int last = 0;
         for(int key: map.keySet())
         {
            rmq.update(key, key, -1*map.get(key));
            last = Math.max(last, key);
         }
         for(int i=0; i < N; i++)
         {
            int temp = track[i];
            if(temp <= last)
            {
               int min = (int)(rmq.minQuery(temp, Q));
               min *= -1;
               arr[i] = Math.max(arr[i], min);
            }
         }
         for(int a: arr)
            System.out.print(a+" ");
      }
   }
   class RangeTree 
   {
		private long[] min;
		private long[] lazy;
		private long[] sum;
		private int size;
		public RangeTree(int size) 
      {
			this.size = size;
			min = new long[4*size];
			sum = new long[4*size];
			lazy = new long[4*size];
		}
		public void update(int l, int r, int inc) 
      {
			update(1, 0, size-1, l, r, inc);
		}
		private void pushDown(int index, int l, int r) 
      {
			min[index] += lazy[index];
			sum[index] += lazy[index] * (r-l+1);
			if(l != r) 
         {
				lazy[2*index] += lazy[index];
				lazy[2*index+1] += lazy[index];
			}
			lazy[index] = 0;
		}
		private void pullUp(int index, int l, int r) 
      {
			int m = (l+r)/2;
			min[index] = Math.min(evaluateMin(2*index, l, m), evaluateMin(2*index+1, m+1, r));
			sum[index] = evaluateSum(2*index, l, m) + evaluateSum(2*index+1, m+1, r);
		}
		private long evaluateSum(int index, int l, int r) 
      {
			return sum[index] + (r-l+1)*lazy[index];
		}
		private long evaluateMin(int index, int l, int r) 
      {
			return min[index] + lazy[index];
		}
		private void update(int index, int l, int r, int left, int right, int inc) 
      {
			if(r < left || l > right) return;
			if(l >= left && r <= right) {
				lazy[index] += inc;
				return;
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			update(2*index, l, m, left, right, inc);
			update(2*index+1, m+1, r, left, right, inc);
			pullUp(index, l, r);
		}
		public long minQuery(int l, int r) 
      {
			return minQuery(1, 0, size-1, l, r);
		}
		private long minQuery(int index, int l, int r, int left, int right) 
      {
			if(r < left || l > right) return Long.MAX_VALUE;
			if(l >= left && r <= right) {
				return evaluateMin(index, l, r);
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			long ret = Long.MAX_VALUE;
			ret = Math.min(ret, minQuery(2*index, l, m, left, right));
			ret = Math.min(ret, minQuery(2*index+1, m+1, r, left, right));
			pullUp(index, l, r);
			return ret;
		}
		public long sumQuery(int l, int r) 
      {
			return sumQuery(1, 0, size-1, l, r);
		}
		private long sumQuery(int index, int l, int r, int left, int right) 
      {
			if(r < left || l > right) return 0;
			if(l >= left && r <= right) {
				return evaluateSum(index, l, r);
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			long ret = 0;
			ret += sumQuery(2*index, l, m, left, right);
			ret += sumQuery(2*index+1, m+1, r, left, right);
			pullUp(index, l, r);
			return ret;
		}
	}
