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;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vvc = vector<vc>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vull = vector<ull>;
constexpr int INF = 2000000000;
constexpr ll INFl = 2000000000ll;
constexpr ll INFll = 2000000000000000000ll;
constexpr ll mod = 1e9 + 7;
struct num {
  num(ll val = 0) : v{val} {
    if (v >= mod) v %= mod;
  };
  ll v;
  operator ll() { return v; };
  num operator+(const num& o) const { return {v + o.v}; };
  num operator-(const num& o) const { return {v - o.v + mod}; };
  num operator*(const num& o) const { return {v * o.v}; };
  num operator+=(const num& o) {
    v = num{v + o.v};
    return *this;
  };
  num operator-=(const num& o) {
    v = num{v - o.v + mod};
    return *this;
  };
  num operator*=(const num& o) {
    v = num{v * o.v};
    return *this;
  };
  num operator!() const {
    num R = 1;
    for (__typeof(v + 1) i = (2); i <= (v + 1); ++i) R *= num{i};
    return R;
  }
  num operator^(ll b) const {
    num R{1}, a{v};
    while (b > 0) {
      if (b & 1) R *= a;
      a *= a, b /= 2;
    }
    return R;
  }
  num operator/(const num& o) const { return (*this) * (o ^ (mod - 2)); }
};
ostream& operator<<(ostream& os, pii x) {
  os << '(' << x.first << ' ' << x.second << ')';
  return os;
}
istream& operator>>(istream& is, pii& x) {
  is >> x.first >> x.second;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& x) {
  for (T& i : x) os << i << ' ';
  return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& x) {
  for (T& i : x) is >> i;
  return is;
}
pii operator+(const pii& A, const pii& B) {
  return {A.first + B.first, A.second + B.second};
}
pii operator-(const pii& A, const pii& B) {
  return {A.first - B.first, A.second - B.second};
}
pii operator-(const pii& A) { return {-A.first, -A.second}; }
template <typename T>
bool maxe(T& A, const T& B) {
  if (B > A) {
    A = B;
    return 1;
  }
  return 0;
}
template <typename T>
bool mine(T& A, const T& B) {
  if (B < A) {
    A = B;
    return 1;
  }
  return 0;
}
struct Treeee {
  vll T;
  int S;
  void setup(int n) {
    for (S = 1; S <= n; S *= 2)
      ;
    T.resize(2 * S, -INF);
    for (__typeof(n - 1) i = (0); i <= (n - 1); ++i) cin >> T[S + i];
  }
  void all(ll x) { maxe(T[1], x); }
  void drop(int v) {
    maxe(T[2 * v], T[v]);
    maxe(T[2 * v + 1], T[v]);
    T[v] = -INF;
  }
  void _set(int v, int x, int val, int l, int r) {
    if (l == r) {
      T[v] = val;
      return;
    }
    drop(v);
    int m = (r + l) / 2;
    if (x <= m)
      _set(2 * v, x, val, l, m);
    else
      _set(2 * v + 1, x, val, m + 1, r);
  }
  void set(int x, int val) { _set(1, x, val, 0, S - 1); }
  void end() {
    for (__typeof(S - 1) i = (1); i <= (S - 1); ++i) drop(i);
  }
} Tree;
int n, q;
bool in() {
  cin >> n;
  Tree.setup(n);
  cin >> q;
  return true;
}
ll solve() {
  while (q-- > 0) {
    int a, b, c;
    cin >> a >> b;
    if (a == 1) {
      cin >> c;
      Tree.set(b - 1, c);
    } else if (a == 2) {
      Tree.all(b);
    } else
      return -'e';
  }
  Tree.end();
  for (__typeof(n - 1) i = (0); i <= (n - 1); ++i)
    cout << Tree.T[Tree.S + i] << " ";
  cout << endl;
  return -INF;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int noOfTests = 1;
  while (noOfTests-- > 0) {
    if (!in()) {
      cout << "popsute wejscie\n";
      continue;
    }
    ll result = solve();
    if (result == ll(-'t'))
      cout << "TAK\n";
    else if (result == ll(-'n'))
      cout << "NIE\n";
    else if (result == ll(-'e'))
      cout << "Popsute\n";
    else if (result != -INF)
      cout << result << '\n';
  }
  return 0;
}
