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.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n,m;
    static long dp[]  ,arr[];
    static boolean[] v;
    static LinkedList<Integer>[] adj;
    static int[] ans;

    public static void main(String[] args) throws IOException{
        Reader.init(System.in);
        int n = Reader.nextInt();
        int[] arr = new int[n];
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0   ;i < n ; i++){
            arr[i] = Reader.nextInt();
        }
        int[] ans = new int[n];
        boolean[] vis = new boolean[n];
        int q = Reader.nextInt();
        int qq = q;
        int max = 0;
        int[][] query = new int[q][3];
        int cnt = 0;
        while (q-->0){
            int x = Reader.nextInt();
            if (x==1){
                query[cnt][0] = x;
                query[cnt][1] = Reader.nextInt()-1;
                query[cnt][2] = Reader.nextInt();
            }
            else{
                query[cnt][0] = x;
                query[cnt][1] = Reader.nextInt();
            }
            //System.out.println(Arrays.deepToString(query));
            cnt++;
        }
        //System.out.println(Arrays.deepToString(query));
        for (int i = qq-1 ; i>= 0 ; i--){
            if (query[i][0]==1){
                if(!vis[query[i][1]]){
                    vis[query[i][1]]=true;
                    if(max < query[i][2]) {
                        ans[query[i][1]] = query[i][2];
                    }
                    else{
                        ans[query[i][1]] = max;
                    }
                }
            }
            else{
                max = Math.max(query[i][1],max);
            }
        }
        for (int i = 0 ; i < n ;i++){
            if (!vis[i]){
                ans[i] = Math.max(max,arr[i]);
            }
        }

        for (int i = 0 ; i < n ; i++){
            System.out.print(ans[i] + " ");
        }
        System.out.println();



    }
}

class TrieNode{

    int[][] next = new int[2][(1000003)*30];
    int[] cnt = new int[(1000003)*30];
    int Idx = 1;
    int value;
    TrieNode[] arr = new TrieNode[2];

    void insert(int n){
        int cur = 0;
        for(int i = 30 - 1; i >= 0; --i) {
            int val = n >> i & 1;
            int nxt = next[val][cur];
            if (nxt == 0)
                nxt = next[val][cur] = Idx++;
            cur = nxt;
            cnt[cur]++;
        }
    }

    int query(int n , int k){
        int num = 0;
        int ans = 0;
        for(int i = 30 - 1; i >= 0; i--) {
            int val = n >> i & 1;
            if (((k >> i) & 1) == 0) {
                if(val==1) {
                    ans += cnt[next[0][num]];
                }
                else{
                    ans += cnt[next[1][num]];
                }
                num = next[val][num];
            }
            else {
                if (val==1) {
                    num = next[0][num];
                }
                else{
                    num = next[1][num];
                }
            }
            if (num == 0) {
                break;
            }
        }
        ans +=cnt[num];
        return ans;
    }

}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}