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
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;

   public class x1199D
   {
      public static void main(String omkar[]) 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, 0);
         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 
         SparseTable rmq = new SparseTable(200005);
         int last = 0;
         int[] tempo = new int[200005];
         for(int key: map.keySet())
         {
            //rmq.update(key, key, -1*map.get(key));
            tempo[key] = -1*map.get(key);
            last = Math.max(last, key);
         }
         rmq.lift(tempo);
         for(int i=0; i < N; i++)
         {
            int temp = track[i];
            //System.out.print(temp+" ");
            if(temp <= last)
            {
               int min = (int)(rmq.query(temp+1, Q+1));
               min *= -1;
               arr[i] = Math.max(arr[i], min);
            }
         }
         for(int a: arr)
            System.out.print(a+" ");
      }
   }
   class SparseTable
   {
      public int[] log;
      public int[][] table;
      public int N;  public int K;
      
      public SparseTable(int N)
      {
         this.N = N;
         log = new int[N+2];
         K = Integer.numberOfTrailingZeros(Integer.highestOneBit(N));
         table = new int[N][K+1];
         sparsywarsy();
      }
      private void sparsywarsy()
      {
         log[1] = 0;
         for(int i=2; i <= N+1; i++)
            log[i] = log[i/2]+1;
      }
      public void lift(int[] arr)
      {
         int n = arr.length;
         for(int i=0; i < n; i++)
            table[i][0] = arr[i];
         for(int j=1; j <= K; j++)
            for(int i=0; i + (1 << j) <= n; i++)
                table[i][j] = Math.min(table[i][j-1], table[i+(1 << (j - 1))][j-1]);
      }
      public int query(int L, int R)
      {
         //inclusive, 1 indexed
         L--;  R--;
         int mexico = log[R-L+1];
         return Math.min(table[L][mexico], table[R-(1 << mexico)+1][mexico]);
      }
   }
