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;
struct node {
  int l, r, v, add;
  node(int l0, int r0, int val) {
    l = l0;
    r = r0;
    v = val;
    add = 0;
  }
  node() { l = r = v = add = 0; }
};
vector<node> tree;
int l;
void push(int i) {
  if (tree[i].l == tree[i].r) {
    tree[i].v = max(tree[i].v, tree[i].add);
    tree[i].add = 0;
    return;
  }
  tree[2 * i].add = max(tree[i].add, tree[2 * i].add);
  tree[2 * i + 1].add = max(tree[i].add, tree[2 * i + 1].add);
  tree[i].add = 0;
  tree[i].v = 1543;
}
void printTree() {
  int cur = 1;
  int rest = 0;
  for (int cnt = 1; cnt < l; ++cnt) {
    if (rest == cur) {
      rest = 1;
      cur *= 2;
      cout << endl;
    } else {
      rest++;
    }
    cout << '(' << tree[cnt].l << ' ' << tree[cnt].r << ' ' << tree[cnt].v
         << " + " << tree[cnt].add << ") ";
  }
  cout << endl;
}
void update(int ql, int qr, int i, int add) {
  if (ql > tree[i].r || qr < tree[i].l) {
    push(i);
    return;
  }
  if (ql <= tree[i].l && qr >= tree[i].r) {
    tree[i].add = max(tree[i].add, add);
    push(i);
    return;
  }
  push(i);
  update(ql, qr, 2 * i, add);
  update(ql, qr, 2 * i + 1, add);
  push(i);
}
void updVal(int i, int q, int v) {
  if (tree[i].l == tree[i].r) {
    push(i);
    tree[i].v = v;
    return;
  }
  push(i);
  if (tree[2 * i + 1].l > q) {
    updVal(2 * i, q, v);
  } else {
    updVal(2 * i + 1, q, v);
  }
}
int getVal(int i, int q) {
  if (tree[i].l == tree[i].r) {
    push(i);
    return tree[i].v;
  }
  push(i);
  if (tree[2 * i + 1].l > q) {
    return getVal(2 * i, q);
  } else {
    return getVal(2 * i + 1, q);
  }
}
void build(int n, vector<int> &ar) {
  l = 1;
  while (l < 2 * n) {
    l *= 2;
  }
  tree.resize(l);
  ar.resize(l >> 1);
  for (int i = l - 1; i > 0; --i) {
    tree[i].add = 0;
    if (i * 2 >= l) {
      tree[i].l = tree[i].r = i;
      tree[i].v = ar[i - (l >> 1)];
    } else {
      tree[i].l = tree[2 * i].l;
      tree[i].r = tree[2 * i + 1].r;
      tree[i].v = 1543;
    }
  }
}
int main() {
  int n, m;
  cin >> n;
  vector<int> ar(n);
  for (int i = 0; i < n; ++i) cin >> ar[i];
  build(n, ar);
  cin >> m;
  char c;
  int p, x;
  int k = (l >> 1);
  for (int i = 0; i < m; ++i) {
    cin >> c;
    if (c == '1') {
      cin >> p >> x;
      p--;
      updVal(1, p + k, x);
    } else {
      cin >> x;
      update(k, l - 1, 1, x);
    }
  }
  for (int i = 0; i < n; ++i) cout << getVal(1, i + k) << ' ';
  cout << endl;
  return 0;
}
