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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DWelfareState solver = new DWelfareState();
        solver.solve(1, in, out);
        out.close();
    }

    static class DWelfareState {
        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            int n = sc.nextInt();
            int N = 1;
            while (N < n) N *= 2;
            int[] arr = new int[N + 1];
            for (int i = 1; i <= n; i++) {
                arr[i] = sc.nextInt();
            }
            SegmentTree st = new SegmentTree(arr);
            int q = sc.nextInt();
            while (q-- > 0) {
                //   pw.println(Arrays.toString(st.sTree));
                int t = sc.nextInt();
                if (t == 1) {
                    int i = sc.nextInt();
                    int x = sc.nextInt();
                    st.update_range1(i, i, x);
                } else {
                    int x = sc.nextInt();
                    st.update_range(1, n, x);
                }
            }
            for (int i = 1; i <= n; i++) pw.print(st.query(i, i) + " ");
        }

        class SegmentTree {
            int N;
            int[] array;
            int[] sTree;
            int[] lazy;

            SegmentTree(int[] in) {
                array = in;
                N = in.length - 1;
                sTree = new int[N << 1];        //no. of nodes = 2*N - 1, we add one to cross out index zero
                lazy = new int[N << 1];
                build(1, 1, N);
            }

            void build(int node, int b, int e) {
                if (b == e)
                    sTree[node] = array[b];
                else {
                    int mid = b + e >> 1;
                    build(node << 1, b, mid);
                    build(node << 1 | 1, mid + 1, e);
                    sTree[node] = Math.max(sTree[node << 1], sTree[node << 1 | 1]);
                }
            }

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

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

            void update_range(int node, int b, int e, int i, int j, int val) {
                if (i > e || j < b)
                    return;
                if (b >= i && e <= j) {
                    sTree[node] = Math.max(sTree[node], val);
                    lazy[node] = Math.max(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] = Math.max(sTree[node << 1], sTree[node << 1 | 1]);
                }

            }

            void update_range1(int node, int b, int e, int i, int j, int val) {
                if (i > e || j < b)
                    return;
                if (b >= i && e <= j) {
                    sTree[node] = val;
                    lazy[node] = val;
                } else {
                    int mid = b + e >> 1;
                    propagate(node, b, mid, e);
                    update_range1(node << 1, b, mid, i, j, val);
                    update_range1(node << 1 | 1, mid + 1, e, i, j, val);
                    sTree[node] = Math.max(sTree[node << 1], sTree[node << 1 | 1]);
                }

            }

            void propagate(int node, int b, int mid, int e) {
                lazy[node << 1] = Math.max(lazy[node << 1], lazy[node]);
                lazy[node << 1 | 1] = Math.max(lazy[node << 1 | 1], lazy[node]);
                sTree[node << 1] = Math.max(sTree[node << 1], lazy[node]);
                sTree[node << 1 | 1] = Math.max(sTree[node << 1 | 1], lazy[node]);
                lazy[node] = 0;
            }

            int query(int i, int j) {
                return query(1, 1, N, i, j);
            }

            int query(int node, int b, int e, int i, int j) {
                if (i > e || j < b)
                    return 0;
                if (b >= i && e <= j)
                    return sTree[node];
                int mid = b + e >> 1;
                propagate(node, b, mid, e);
                int q1 = query(node << 1, b, mid, i, j);
                int q2 = query(node << 1 | 1, mid + 1, e, i, j);
                return Math.max(q1, q2);

            }

        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

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

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

    }
}

