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
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int infi = 2147483600;
const long long infl = 1e17;
struct SegmentTree {
 private:
  int N;
  vector<long long> node;
  long long e;

 public:
  SegmentTree() {}
  SegmentTree(long long e) : e(e) {}
  void __init__(int sz) {
    N = 1;
    while (N < sz) N *= 2;
    node.resize(2 * N - 1, e);
  }
  void build(vector<long long> &v) {
    int sz = int(v.size());
    __init__(sz);
    for (long long i = 0; i < (long long)sz; i++) {
      node[i + N - 1] = v[i];
    }
    for (int i = N - 2; i >= 0; i--) {
      node[i] = max(node[i * 2 + 1], node[i * 2 + 2]);
    }
  }
  void update(int k, long long x) {
    k += N - 1;
    node[k] = x;
    while (k > 0) {
      k = (k - 1) / 2;
      node[k] = max(node[2 * k + 1], node[2 * k + 2]);
    }
  }
  long long query(int a, int b) { return query(a, b, 0, 0, N); }
  long long query(int a, int b, int k, int l, int r) {
    if (b <= l || r <= a) return e;
    if (a <= l && r <= b) return node[k];
    long long vl, vr;
    vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
    vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
    return max(vl, vr);
  }
  void recalc() {
    for (long long k = 0; k < (long long)N - 1; k++) {
      node[2 * k + 1] = max(node[2 * k * 1], node[k]);
      node[2 * k + 2] = max(node[2 * k * 2], node[k]);
    }
  }
  long long show_one(int i) {
    if (0 <= i && i < N) return node[i + N - 1];
    return e;
  }
  void view() {
    for (long long k = (long long)N - 1; k < (long long)2 * N - 1; k++) {
      if (node[k] == e)
        cout << "inf ";
      else
        cout << node[k] << " ";
    }
    cout << endl;
    return;
  }
};
int main() {
  long long n;
  cin >> n;
  vector<long long> a(n);
  for (long long i = 0; i < (long long)n; i++) cin >> a[i];
  long long q;
  cin >> q;
  SegmentTree payoff(0);
  payoff.__init__(q);
  vector<long long> last_buy(n, -1);
  for (long long i = 0; i < (long long)q; i++) {
    int c;
    cin >> c;
    if (c == 1) {
      long long p, x;
      cin >> p >> x;
      p--;
      a[p] = x;
      last_buy[p] = i;
    } else {
      long long x;
      cin >> x;
      payoff.update(i, x);
    }
  }
  for (long long i = 0; i < (long long)n; i++) {
    cout << max(a[i], payoff.query(last_buy[i] + 1, q)) << " ";
  }
  cout << endl;
}
