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.util.*;
import java.io.*;
import java.util.Map.Entry;

public class Codeforces {

    public static class SegmentTree {        // 1-based DS, OOP

        int N;            //the number of elements in the array as a power of 2 (i.e. after padding)
        int[] array, sTree, 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)    // O(n)
        {
            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_point(int index, int val)            // O(log n)
        {
            index += N - 1;
            sTree[index] = val;
            while (index > 1) {
                index >>= 1;
                sTree[index] = Math.max(sTree[index << 1], sTree[index << 1 | 1]);
            }
        }


        void update_range(int i, int j, int val)        // O(log n)
        {
            update_range(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] += (e - b + 1) * val;
                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 propagate(int node, int b, int mid, int e) {
            lazy[node << 1] += lazy[node];
            lazy[node << 1 | 1] += lazy[node];
            sTree[node << 1] += lazy[node];
            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)    // O(log n)
        {
            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);

        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int[] start = new int[n];
        int q = Integer.parseInt(br.readLine());
        int N = 1;
        while(N < q){
            N <<= 1;
        }
        int[] in = new int[N + 1];
        SegmentTree updates = new SegmentTree(in);
        for(int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            if (t == 2) {
                updates.update_point(i + 1, Integer.parseInt(st.nextToken()));
            } else {
                int p = Integer.parseInt(st.nextToken());
                int x = Integer.parseInt(st.nextToken());
                start[p - 1] = i;
                arr[p - 1] = x;
            }
        }
        for(int i = 0; i < n; i++){
            arr[i] = Math.max(arr[i], updates.query(start[i] + 1, q));
        }
        for(int i = 0; i < n; i++){
            pw.print(arr[i] + " ");
        }
        pw.println();
//        pw.println(Arrays.toString(start));
        pw.flush();
        pw.close();
    }
}