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;
template <class T>
inline T mod_v(T num) {
  if (num >= 0)
    return num % 1000000007;
  else
    return (num % 1000000007 + 1000000007) % 1000000007;
}
template <class T>
inline T gcd(T a, T b) {
  a = abs(a);
  b = abs(b);
  while (b) b ^= a ^= b ^= a %= b;
  return a;
}
template <class T>
T fast_pow(T n, T p) {
  if (p == 0) return 1;
  if (p % 2) {
    T g = mod_v(mod_v(n) * mod_v(fast_pow(n, p - 1)));
    return g;
  } else {
    T g = fast_pow(n, p / 2);
    g = mod_v(mod_v(g) * mod_v(g));
    return g;
  }
}
template <class T>
inline T modInverse(T n) {
  return fast_pow(n, 1000000007 - 2);
}
bool equalTo(double a, double b) {
  if (fabs(a - b) <= 1e-9)
    return true;
  else
    return false;
}
bool notEqual(double a, double b) {
  if (fabs(a - b) > 1e-9)
    return true;
  else
    return false;
}
bool lessThan(double a, double b) {
  if (a + 1e-9 < b)
    return true;
  else
    return false;
}
bool lessThanEqual(double a, double b) {
  if (a < b + 1e-9)
    return true;
  else
    return false;
}
bool greaterThan(double a, double b) {
  if (a > b + 1e-9)
    return true;
  else
    return false;
}
bool greaterThanEqual(double a, double b) {
  if (a + 1e-9 > b)
    return true;
  else
    return false;
}
struct debugger {
  template <typename T>
  debugger& operator,(const T& v) {
    cerr << v << " ";
    return *this;
  }
} dbg;
int nextInt() {
  int n;
  scanf("%d", &n);
  return n;
}
long long nextLong() {
  long long n;
  scanf("%lld", &n);
  return n;
}
void print(int n) { printf("%d", n); }
void println(int n) { printf("%d\n", n); }
void println(long long n) { printf("%lld\n", n); }
template <class T>
inline int in(register T& num) {
  register char c = 0;
  num = 0;
  bool n = false;
  while (c < 33) c = getchar();
  while (c > 33) {
    if (c == '-')
      n = true;
    else
      num = num * 10 + c - '0';
    c = getchar();
  }
  num = n ? -num : num;
  return 1;
}
int ara[2 * 100006];
int lastUpdateDoneAt[2 * 100005];
int tree[4 * 2 * 100005];
int n, q;
void update(int node, int l, int r, int idx, int val) {
  if (idx < l or r < idx) return;
  if (l == r) {
    tree[node] = val;
    return;
  }
  int mid = (l + r) >> 1;
  int left = node << 1;
  int right = left | 1;
  update(left, l, mid, idx, val);
  update(right, mid + 1, r, idx, val);
  tree[node] = max(tree[left], tree[right]);
  return;
}
int query(int node, int l, int r, int u, int v) {
  if (v < l or r < u) return 0;
  if (u <= l && r <= v) {
    return tree[node];
  }
  int mid = (l + r) >> 1;
  int left = node << 1;
  int right = left | 1;
  return max(query(left, l, mid, u, v), query(right, mid + 1, r, u, v));
}
int main() {
  in(n);
  for (int i = 1; i <= n; i++) in(ara[i]);
  in(q);
  int typ;
  for (int i = 1; i <= q; i++) {
    in(typ);
    if (typ == 1) {
      int p, val;
      in(p), in(val);
      ara[p] = val;
      lastUpdateDoneAt[p] = i;
    } else {
      int val;
      in(val);
      update(1, 1, q, i, val);
    }
  }
  for (int i = 1; i <= n; i++) {
    auto val = query(1, 1, q, lastUpdateDoneAt[i] + 1, q);
    ara[i] = max(ara[i], val);
    printf("%d ", ara[i]);
  }
  return 0;
}
