You are given an array a consisting of n integers. You have to process q queries to this array; each query is given as four numbers l, r, x and y, denoting that for every i such that l ≤ i ≤ r and ai = x you have to set ai equal to y.

Print the array after all queries are processed.

Input

The first line contains one integer n (1 ≤ n ≤ 200000) — the size of array a.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100) — the elements of array a.

The third line contains one integer q (1 ≤ q ≤ 200000) — the number of queries you have to process.

Then q lines follow. i-th line contains four integers l, r, x and y denoting i-th query (1 ≤ l ≤ r ≤ n, 1 ≤ x, y ≤ 100).

Output

Print n integers — elements of array a after all changes are made.

Example

Input

5
1 2 3 4 5
3
3 5 3 5
1 5 5 1
1 5 1 5


Output

5 2 5 4 5 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;
const ll inf = (1e18);
const ll mod = 1000000007;
const vector<int> dy = {-1, 0, 1, 0}, dx = {0, -1, 0, 1};
struct __INIT {
  __INIT() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} __init;
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
void debag(const T &a) {
  cerr << "debag :";
  for (auto v : a) cerr << v << " ";
  cerr << "\n";
}
template <class T>
void print(const T &a) {
  for (auto v : a) cout << v << " ";
  cout << "\n";
}
template <typename T>
struct ST {
  using F = function<T(T &a, T &b)>;
  int n;
  F f;
  T ti;
  vector<T> dat;
  ST(){};
  ST(F f, T ti) : f(f), ti(ti) {}
  void init(int n_) {
    n = 1;
    while (n < n_) n <<= 1;
    dat.assign(n << 1, ti);
  }
  void build(const vector<T> &v) {
    int n_ = v.size();
    init(n_);
    for (int i = 0; i < n_; i++) dat[n + i] = v[i];
    for (int i = n - 1; i; i--)
      dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);
  }
  void set_val(int k, T x) {
    dat[k += n] = x;
    while (k >>= 1) dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
  }
  void update(int k, int x, int y) {
    k += n;
    dat[k][x] = y;
    while (k >>= 1) dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
  }
  T query(int a, int b) {
    T vl = ti, vr = ti;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
};
int main() {
  int n;
  cin >> n;
  V<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  int q;
  cin >> q;
  V<V<int>> in(n), out(n);
  V<int> x(q), y(q);
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r >> x[i] >> y[i];
    l--;
    r--;
    x[i]--;
    y[i]--;
    in[l].emplace_back(i);
    out[r].emplace_back(i);
  }
  array<int, 100> E;
  for (int i = 0; i < 100; i++) E[i] = i;
  auto f = [&](array<int, 100> &a, array<int, 100> &b) {
    array<int, 100> c;
    for (int i = 0; i < 100; i++) c[i] = b[a[i]];
    return c;
  };
  ST<array<int, 100>> dp(f, E);
  dp.init(q + 5);
  for (int i = 0; i < n; i++) {
    for (int v : in[i]) {
      dp.update(v, x[v], y[v]);
    }
    cout << dp.dat[1][a[i]] + 1 << (i == n - 1 ? "\n" : " ");
    for (int v : out[i]) dp.update(v, x[v], x[v]);
  }
}
