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
//package codeforces.practice.oneVone.Oct22_2020;

import java.io.*;
import java.util.*;

public class B1198 {
    static InputReader in;
    static PrintWriter out;

    public static void main(String[] args) {
        //initReaderPrinter(true);
        initReaderPrinter(false);
        //solve(in.nextInt());
        solve(1);
    }

    static void solve(int testCnt) {
        for (int testNumber = 0; testNumber < testCnt; testNumber++) {
            int n = in.nextInt();
            int[] a = new int[n];
            for(int i = 0; i < n; i++) {
                a[i] = in.nextInt();
            }
            int q = in.nextInt();
            int[][] t1 = new int[n][2];
            for(int i = 0; i < n; i++) {
                t1[i][0] = -1;
                t1[i][1] = a[i];
            }
            int[] t2 = new int[q];
            for(int i = 0; i < q; i++) {
                int t = in.nextInt();
                if(t == 1) {
                    int p = in.nextInt() - 1;
                    int x = in.nextInt();
                    t1[p][0] = i;
                    t1[p][1] = x;
                }
                else {
                    int x = in.nextInt();
                    t2[i] = x;
                }
            }
            RangeMaxQuery_SparseTable rmq = new RangeMaxQuery_SparseTable(t2);
            for(int i = 0; i < n; i++) {
                int balance = Math.max(t1[i][1], rmq.query(t1[i][0] + 1, q - 1));
                out.print(balance + " ");
            }
            out.println();
        }
        out.close();
    }

    static class RangeMaxQuery_SparseTable {
        int n, k;
        int[] log;
        int[][] rangeMax;

        public RangeMaxQuery_SparseTable(int[] a) {
            n = a.length;
            log = new int[n + 1];
            log[1] = 0;
            for(int i = 2; i <= n; i++) {
                log[i] = log[i / 2] + 1;
            }
            k = log[n];
            rangeMax = new int[n][k + 1];
            for(int i = 0; i < n; i++) {
                rangeMax[i][0] = a[i];
            }
            for(int j = 1; j <= k; j++) {
                for(int i = 0; i + (1 << j) <= n; i++) {
                    rangeMax[i][j] = Math.max(rangeMax[i][j - 1], rangeMax[i + (1 << (j - 1))][j - 1]);
                }
            }
        }

        public int query(int L, int R) {
            if(L >= n) {
                return 0;
            }
            int j = log[R - L + 1];
            return Math.max(rangeMax[L][j], rangeMax[R - (1 << j) + 1][j]);
        }
    }

    static void initReaderPrinter(boolean test) {
        if (test) {
            try {
                in = new InputReader(new FileInputStream("src/input.in"));
                out = new PrintWriter(new FileOutputStream("src/output.out"));
            } catch (IOException e) {
                e.printStackTrace();
            }
        } else {
            in = new InputReader(System.in);
            out = new PrintWriter(System.out);
        }
    }

    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        InputReader(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream), 32768);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

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

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        Integer[] nextIntArray(int n) {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        Long[] nextLongArray(int n) {
            Long[] a = new Long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }
    }
}


