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

public class Main implements Runnable {
  static ContestScanner in;
  static Writer out;

  public static void main(String[] args) {
    new Thread(null, new Main(), "", 16 * 1024 * 1024).start();
  }

  public void run() {
    Main main = new Main();
    try {
      in = new ContestScanner();
      out = new Writer();
      main.solve();
      out.close();
      in.close();
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  void solve() throws IOException {
    int n = in.nextInt();
    long[] a = new long[n];
    int[] checkTime = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = in.nextLong();
      checkTime[i] = -1;
    }
    int q = in.nextInt();
    long[] payoff = new long[q + 1];
    for (int i = 0; i < q; i++) {
      int flag = in.nextInt();
      if (flag == 1) {
        int who = in.nextInt() - 1;
        int have = in.nextInt();
        a[who] = have;
        checkTime[who] = i;
      } else {
        payoff[i] = in.nextInt();
      }
    }
    for (int i = q - 2; i >= 0; i--) {
      payoff[i] = Math.max(payoff[i], payoff[i + 1]);
    }
    for (int i = 0; i < n; i++) {
      if (i > 0)
        out.print(" ");
      out.print(Math.max(payoff[checkTime[i] + 1], a[i]));
    }
    out.println();
  }
}

class Writer extends PrintWriter {
  public Writer(String filename) throws IOException {
    super(new BufferedWriter(new FileWriter(filename)));
  }

  public Writer() throws IOException {
    super(System.out);
  }
}

class ContestScanner implements Closeable {
  private BufferedReader in;
  private int c = -2;

  public ContestScanner() throws IOException {
    in = new BufferedReader(new InputStreamReader(System.in));
  }

  public ContestScanner(String filename) throws IOException {
    in = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
  }

  public String nextToken() throws IOException {
    StringBuilder sb = new StringBuilder();
    while ((c = in.read()) != -1 && Character.isWhitespace(c))
      ;
    while (c != -1 && !Character.isWhitespace(c)) {
      sb.append((char) c);
      c = in.read();
    }
    return sb.toString();
  }

  public String readLine() throws IOException {
    StringBuilder sb = new StringBuilder();
    if (c == -2)
      c = in.read();
    while (c != -1 && c != '\n' && c != '\r') {
      sb.append((char) c);
      c = in.read();
    }
    return sb.toString();
  }

  public long nextLong() throws IOException, NumberFormatException {
    return Long.parseLong(nextToken());
  }

  public int nextInt() throws NumberFormatException, IOException {
    return (int) nextLong();
  }

  public double nextDouble() throws NumberFormatException, IOException {
    return Double.parseDouble(nextToken());
  }

  public void close() throws IOException {
    in.close();
  }
}
