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

public class betterWelfareState {
    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];
        for (int i = 0; i < N; i++) {
            money[i] = sc.nextInt();
        }

        int Q = sc.nextInt();
        /*
         One approach: Solving with a well-kept time-sequenced set of information
         about the most valuable "raising event" at a given time point.
         Basically, we only want to keep the most important events.
         New payout events necessarily have greater accessibility for prior points (it can
         override more forced updates)
         Thus, if it has greater value than prior raises, we can DEFINITELY delete all of those prior, lesser
         raises. On the other hand, if it has a lower value, then we still can't rule it out
         since it has greater accessibility. What results is a graph that is strictly decreasing,
         and this appropiately provides us with the necessary info to determine the
         amount of money each person has at the end. They will take the highest point to the right of them
         With this construction, any person will always take the thing immediately available in our decreasing graph
         The nearest point to the right!
         */
        int[] lastExpenseTime = new int[N];
        Arrays.fill(lastExpenseTime, -1);
        TreeMap<Integer, Integer> raiseEvents = new TreeMap<>();
        for (int i = 0; i < Q; i++) {
            int type = sc.nextInt();
            if (type == 1) {
                // This is forced, nothing we can do
                int person = sc.nextInt() - 1;
                int amount = sc.nextInt();
                money[person] = amount;
                lastExpenseTime[person] = i;
            }
            else if (type == 2) {
                // Now let's process our events to create a decreasing graph
                int amount = sc.nextInt();
                // We keep polling until we reach the base case where we have more accessibility
                // but possibly less value than previous events
                while (raiseEvents.size() > 0 && amount >= raiseEvents.lastEntry().getValue()) {
                    raiseEvents.pollLastEntry();
                }
                raiseEvents.put(i, amount);
            }
        }

        for (int person = 0; person < N; person++) {
            if (lastExpenseTime[person] == -1) {
                // If never updated, we just take the
                if (raiseEvents.firstEntry() != null) {
                    int highest = raiseEvents.firstEntry().getValue();
                    out.print(Math.max(money[person], highest) + " ");
                }
                else {
                    out.print(money[person] + " ");
                }
            }
            else {
                int timePoint = lastExpenseTime[person];
                // There is a case where we have no access to higher items
                if (raiseEvents.higherKey(timePoint) != null) {
                    int nextHighest = raiseEvents.get(raiseEvents.higherKey(timePoint));
                    out.print(Math.max(money[person], nextHighest) + " ");
                }
                else {
                    out.print(money[person] + " ");
                }
            }
        }
        out.println();
        out.close();
    }

    static void solveWithQuery(int Q, Scanner sc) {


    }

    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());
        }
    }
}
