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
/*
 * @author derrick20
 * Second Approach, with Max Queries after the events have been read in.
 * Different thinking style, compounding on top of work we've already done
 * to efficiently get information for each person
 */
import java.io.*;
import java.util.*;

public class alsoGoodWelfare {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int[] money = new int[N + 1];
        // Person i's money, 1-indexed!
        for (int i = 1; i <= N; i++) {
            money[i] = sc.nextInt();
        }

        int Q = sc.nextInt();
        int[] lastTime = new int[N + 1];
        // WE DO NOT NEED A NEW ARRAY TO STORE EXPENSE AMOUNTS
        // JUST USE THE OLD MONEY ARRAY!!!!
        // Second array stores time of the latest event

        int[] payouts = new int[Q + 1]; // at a certain time, what payout happened?
        for (int time = 1; time <= Q; time++) {
            int type = sc.nextInt();
            if (type == 1) {
                int person = sc.nextInt();
                int amount = sc.nextInt();
                money[person] = amount;
                lastTime[person] = time;
            }
            else {
                int amount = sc.nextInt();
                payouts[time] = amount;
            }
        }

        int[] suffixMax = new int[Q + 1];
        // It is a suffix because a person can only rely
        // on bailouts that happen later in time relative to their
        // last forced spending!
        // Stores the MAX amount of bailout that happens at time >= time t
        suffixMax[Q] = payouts[Q];
        for (int time = Q - 1; time >= 1; time--) {
            // We can either look to a previously discovered maximum
            // OR we could use the max available at the current time period
            // Which could likely be just 0!
            suffixMax[time] = Math.max(suffixMax[time + 1], payouts[time]);
        }
//        System.out.println(Arrays.toString(suffixMax));
//        System.out.println(Arrays.toString(money));
        for (int person = 1; person <= N; person++) {
            // we want to see, after the last forced expense, is there
            // a better payout that we can use!
            int laterPay;
            if (lastTime[person] == 0) {
                laterPay = suffixMax[1]; // Use all the time from 1 on!
            }
            else {
                laterPay = suffixMax[lastTime[person]];
            }
            out.print(Math.max(money[person], laterPay) + " ");
        }
        out.println();
        out.close();
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

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

        FastScanner(FileReader s) {
            br = new BufferedReader(s);
        }

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

        String nextLine() throws IOException {
            return br.readLine();
        }

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

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

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