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>
auto clk = clock();
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
const int dx8[] = {-1, -1, -1, 0, 1, 1, 1, 0},
          dy8[] = {-1, 0, 1, 1, 1, 0, -1, -1};
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long Gcd(long long a, long long b) {
  if (a % b == 0) return b;
  return Gcd(b, a % b);
}
long long Max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long Min(long long a, long long b) {
  if (a < b) return a;
  return b;
}
void printvector(std::vector<long long> v) {
  for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
  }
  cout << "" << endl;
}
void printarray(long long a[], long long n) {
  for (long long i = 0; i < n; ++i) {
    cout << a[i] << " ";
  }
  cout << "" << endl;
}
long long findlcm(vector<long long> arr, long long n) {
  long long ans = arr[0];
  for (int i = 1; i < n; i++) ans = (((arr[i] * ans)) / (Gcd(arr[i], ans)));
  return ans;
}
long long gcdExtended(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long x1, y1;
  long long gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long modInverse(long long a, long long m) {
  long long x, y;
  long long g = gcdExtended(a, m, &x, &y);
  if (g != 1)
    return -1;
  else {
    long long res = (x % m + m) % m;
    return res;
  }
}
long long inverse(long long x, long long mod) { return power(x, mod - 2, mod); }
vector<long long> primeFactors(long long n) {
  vector<long long> v;
  while (n % 2 == 0) {
    v.push_back(2);
    n = n / 2;
  }
  for (int i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      v.push_back(i);
      n = n / i;
    }
  }
  if (n > 2) v.push_back(n);
  return v;
}
long long lowerbound(long long k, vector<long long> v) {
  long long l = 0;
  long long size = v.size();
  long long r = size - 1;
  long long mid;
  while (l <= r) {
    mid = (l + r) / 2;
    if (v[mid] < k)
      l = mid + 1;
    else {
      r = mid - 1;
    }
  }
  return l;
}
long long upperbound(long long k, vector<long long> v) {
  long long l = 0;
  long long size = v.size();
  long long r = size - 1;
  long long mid;
  while (l <= r) {
    mid = (l + r) / 2;
    if (v[mid] > k)
      r = mid - 1;
    else {
      l = mid + 1;
    }
  }
  return l;
}
long long C[2001][2000];
void binomialCoeff(long long n, long long k) {
  long long i, j;
  for (i = 0; i <= n; i++) {
    for (j = 0; j <= k; j++) {
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = (C[i - 1][j - 1] % 1000000007 + C[i - 1][j] % 1000000007) %
                  1000000007;
    }
  }
}
string convertToNewString(const string &s) {
  string newString = "@";
  for (long long i = 0; i < s.size(); i++) {
    newString += "#" + s.substr(i, 1);
  }
  newString += "#$";
  return newString;
}
string longestPalindromeSubstring(const string &s) {
  string Q = convertToNewString(s);
  long long c = 0, r = 0;
  long long P[Q.size() + 4];
  memset(P, 0, sizeof(P));
  for (long long i = 1; i < Q.size() - 1; i++) {
    long long iMirror = c - (i - c);
    if (r > i) {
      P[i] = min(r - i, P[iMirror]);
    }
    while (Q[i + 1 + P[i]] == Q[i - 1 - P[i]]) {
      P[i]++;
    }
    if (i + P[i] > r) {
      c = i;
      r = i + P[i];
    }
  }
  int maxPalindrome = 0;
  int centerIndex = 0;
  for (int i = 1; i < Q.size() - 1; i++) {
    if (P[i] > maxPalindrome) {
      maxPalindrome = P[i];
      centerIndex = i;
    }
  }
  cout << maxPalindrome << "\n";
  return s.substr((centerIndex - 1 - maxPalindrome) / 2, maxPalindrome);
}
long long spf[100010];
void sieve() {
  spf[1] = 1;
  for (int i = 2; i < 100010; i++) spf[i] = i;
  for (int i = 4; i < 100010; i += 2) spf[i] = 2;
  for (int i = 3; i * i < 100010; i++) {
    if (spf[i] == i) {
      for (int j = i * i; j < 100010; j += i)
        if (spf[j] == j) spf[j] = i;
    }
  }
}
long long binarySearch(long long arr[], long long l, long long r, long long x) {
  if (r >= l) {
    long long mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
  }
  return -1;
}
const long long N = 100000;
long long n;
long long tree[2 * N];
void build(long long arr[]) {
  for (long long i = 0; i < n; i++) {
    tree[n + i] = arr[i];
  }
  for (long long i = n - 1; i > 0; --i) {
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
  }
}
void updateTreeNode(long long p, long long value) {
  tree[p + n] = value;
  p = p + n;
  for (long long i = p; i > 1; i >>= 1) {
    tree[i >> 1] = tree[i] + tree[i ^ 1];
  }
}
long long query(long long l, long long r) {
  long long res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      res += tree[l++];
    }
    if (r & 1) {
      res += tree[--r];
    }
  }
  return res;
}
vector<long long> shortPath(vector<pair<long long, long long>> v[],
                            long long src, long long V = 0) {
  set<pair<long long, long long>> setds;
  long long sizee = V;
  long long IN = LLONG_MAX;
  vector<long long> dist(sizee, IN);
  setds.insert(make_pair(0, src));
  dist[src] = 0;
  while (!setds.empty()) {
    pair<long long, long long> tmp = *(setds.begin());
    setds.erase(setds.begin());
    long long u = tmp.second;
    vector<pair<long long, long long>>::iterator i;
    for (i = v[u].begin(); i != v[u].end(); ++i) {
      long long v = (*i).first;
      long long weight = (*i).second;
      if (dist[v] > dist[u] + weight) {
        if (dist[v] != LLONG_MAX)
          setds.erase(setds.find(make_pair(dist[v], v)));
        dist[v] = dist[u] + weight;
        setds.insert(make_pair(dist[v], v));
      }
    }
  }
  return dist;
}
long long root(long long a[], long long r) {
  if (a[r] == r) {
    return r;
  } else {
    long long x = root(a, a[r]);
    a[r] = x;
    return x;
  }
}
void unio(long long a[], long long size[], long long x, long long y) {
  x = root(a, x);
  y = root(a, y);
  if (x == y) {
    return;
  }
  if (size[x] >= size[y]) {
    a[y] = x;
    size[x] += size[y];
  } else {
    a[x] = y;
    size[y] += size[x];
  }
}
void dfs(std::vector<long long> v[], long long s, bool visited[]) {
  visited[s] = true;
  for (long long i = 0; i < v[s].size(); ++i) {
    if (!visited[v[s][i]]) {
      dfs(v, v[s][i], visited);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long txt = 1;
  cin >> n;
  vector<long long> ar(n);
  for (int i = 0, _n = (n); i < _n; i++) cin >> ar[i];
  cin >> txt;
  long long mi = -1;
  long long ind;
  vector<long long> vis(n, 0);
  vector<long long> v[txt];
  long long xl = 0;
  deque<pair<long long, long long>> dq;
  while (xl < txt) {
    long long x69;
    cin >> x69;
    if (x69 == 1) {
      long long p, x;
      cin >> p >> x;
      v[xl].push_back(x69);
      v[xl].push_back(p - 1);
      v[xl].push_back(x);
      xl++;
      continue;
    }
    long long x;
    cin >> x;
    v[xl].push_back(x69);
    v[xl].push_back(x);
    while (dq.empty() == false && dq.front().first < x) {
      dq.pop_front();
    }
    dq.push_front({x, xl});
    xl++;
  }
  long long now;
  long long mx;
  if (!dq.empty()) {
    now = dq.back().second;
    mi = dq.back().first;
    mx = dq.back().first;
  } else {
    now = txt + 1;
    mx = 0;
  }
  long long ko = 0;
  for (long long i = 0; i < txt;) {
    long long j = i;
    while (j < txt && j != now) {
      if (v[j].size() == 3) {
        vis[v[j][1]] = true;
        ar[v[j][1]] = max(mi, v[j][2]);
      }
      j++;
    }
    if (j == now) {
      dq.pop_back();
      if (dq.empty())
        ko = 1, mi = 0;
      else {
        now = dq.back().second;
        mi = dq.back().first;
      }
      j++;
    }
    i = j;
  }
  for (long long i = 0; i < n; i++) {
    if (vis[i]) {
      cout << ar[i] << " ";
    } else {
      cout << max(mx, ar[i]) << " ";
    }
  }
  cout << endl;
}
