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

public class D {

    private void solve() {
        int n = IO.nextInt();
        int a[] = IO.nextIntArray(n);
        int q = IO.nextInt();

        List<Integer> all_time = new ArrayList<>();
        List<Integer> all_amount = new ArrayList<>();

        Map<Integer,Recipe> person = new HashMap<>();

        for(int i=0; i<n; i++) {
            person.put(i, new Recipe(-1, i, a[i]));
        }

        for(int i=0; i<q; i++) {
            if(IO.nextInt()==1) {
                int p = IO.nextInt()-1;
                int x = IO.nextInt();
                person.put(p, new Recipe(i, p, x));

            } else
            {
                int x = IO.nextInt();
                all_time.add(i);
                all_amount.add(x);
            }
        }

        List<Recipe> ordered = new ArrayList<>(person.values());
        ordered.sort(Comparator.comparingInt(r -> r.time));

        int max = (int) -1e9;
        for(int i=all_time.size()-1; i>=0; i--) {
            while(ordered.size() > 0 && ordered.get(ordered.size()-1).time > all_time.get(i)) {
                a[ordered.get(ordered.size()-1).who] = Math.max(ordered.get(ordered.size()-1).amount, max);
                ordered.remove(ordered.size()-1);
            }
            max = Math.max(max, all_amount.get(i));
        }

        for (Recipe recipe : ordered) {
            a[recipe.who] = Math.max(max, recipe.amount);
        }

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

    static class Recipe {
        int time;
        int who;
        int amount;

        public Recipe(int time, int who, int amount) {
            this.time = time;
            this.who = who;
            this.amount = amount;
        }


    }

    //*************
    //*************
    //TEMPLATE CODE

    static long MOD = 0;

    public static void main(String[] args) {
        D instance = new D();
        int testcases = 1;//IO.nextInt();
        while(testcases-->0)
            instance.solve();
    }

    static class IO {
        private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        private static StringTokenizer st;

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

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

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

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

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

        static long[] nextLongArray(int size) {
            long a[] = new long[size];
            for (int i = 0; i < size; i++)
                a[i] = nextLong();
            return a;
        }

        static double[] nextDoubleArray(int size) {
            double a[] = new double[size];
            for (int i = 0; i < size; i++)
                a[i] = nextDouble();
            return a;
        }
    }
}