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>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
template <typename T, bool MULTI = false, typename SIZE_T = int>
struct sms_mo {
  static_assert(std::is_integral<T>::value, "Not an integral type");
  static_assert(std::is_integral<SIZE_T>::value, "Not an integral type");
  struct node {
    node* ch[2];
    SIZE_T cnt;
    char d;
    T v, mi;
    node(int d_, T v_, SIZE_T cnt_) : cnt(cnt_), d(d_), v(v_), mi(v) {
      ch[0] = ch[1] = NULL;
    }
    node(node* x) : cnt(x->cnt), d(x->d), v(x->v), mi(x->mi) {
      ch[0] = x->ch[0], ch[1] = x->ch[1];
    }
    void update() {
      if (!ch[0] ^ !ch[1]) {
        for (int i = 0; i < 2; i++)
          if (ch[i]) {
            node* tmp = ch[i];
            ch[0] = tmp->ch[0], ch[1] = tmp->ch[1];
            d = tmp->d, v = tmp->v;
            cnt = tmp->cnt, mi = tmp->mi;
            delete tmp;
            return;
          }
      }
      cnt = 0;
      mi = std::numeric_limits<T>::max();
      for (int i = 0; i < 2; i++)
        if (ch[i]) {
          cnt += ch[i]->cnt;
          mi = std::min(mi, ch[i]->mi);
        }
    }
  };
  node* root;
  T N;
  char n;
  sms_mo() : root(NULL), N(0), n(0) {}
  sms_mo(T v) : sms_mo() {
    while (v >> n) n++, N = 2 * N + 1;
  }
  sms_mo(const sms_mo& t) : root(NULL), N(t.N), n(t.n) {
    for (SIZE_T i = 0; i < t.size(); i++) {
      T at = t[i];
      SIZE_T qt = t.count(at);
      insert(at, qt);
      i += qt - 1;
    }
  }
  sms_mo(std::initializer_list<T> v) : sms_mo() {
    for (T i : v) insert(i);
  }
  ~sms_mo() {
    std::vector<node*> q = {root};
    while (q.size()) {
      node* x = q.back();
      q.pop_back();
      if (!x) continue;
      q.push_back(x->ch[0]), q.push_back(x->ch[1]);
      delete x;
    }
  }
  friend void swap(sms_mo& a, sms_mo& b) {
    std::swap(a.root, b.root), std::swap(a.N, b.N), std::swap(a.n, b.n);
  }
  SIZE_T size() const { return root ? root->cnt : 0; }
  SIZE_T count(node* x) const { return x ? x->cnt : 0; }
  void clear() {
    sms_mo tmp;
    swap(*this, tmp);
  }
  void expand(T v) {
    while (v >> n) n++, N = 2 * N + 1;
  }
  char msb(T v, char l, char r) {
    for (char i = r; i > l; i--)
      if (v >> i & 1) return i;
    return -1;
  }
  void cut(node* at, T v, char i, node* prev = NULL) {
    char d = msb(v ^ at->v, prev ? std::max(at->d, prev->d) : at->d, i);
    if (d == -1) {
      if (!prev or prev->d <= at->d) return;
      d = prev->d, v = ~at->v;
    }
    node* nxt = new node(at);
    at->ch[v >> d & 1] = NULL;
    at->ch[!(v >> d & 1)] = nxt;
    at->d = d;
  }
  node* insert(node* at, T v, SIZE_T qt, char i) {
    if (!at) return new node(-1, v, qt);
    cut(at, v, i);
    if (at->d == -1) {
      at->cnt += qt;
      at->mi = v;
      if (!MULTI) at->cnt = 1;
      return at;
    }
    bool dir = v >> at->d & 1;
    at->ch[dir] = insert(at->ch[dir], v, qt, at->d - 1);
    at->update();
    return at;
  }
  void insert(T v, SIZE_T qt = 1) {
    if (qt <= 0) return erase(v, -qt);
    expand(v);
    root = insert(root, v, qt, n - 1);
  }
  node* erase(node* at, T v, SIZE_T qt, char i) {
    if (!at) return at;
    if (at->d == -1)
      at->cnt = at->cnt < qt ? 0 : at->cnt - qt;
    else {
      bool dir = v >> at->d & 1;
      at->ch[dir] = erase(at->ch[dir], v, qt, i - 1);
      at->update();
    }
    if (!at->cnt) delete at, at = NULL;
    return at;
  }
  void erase(T v, SIZE_T qt = 1) {
    if (v < 0 or v > N or !qt) return;
    if (qt < 0) insert(v, -qt);
    if (!count(v)) return;
    root = erase(root, v, qt, n - 1);
  }
  void erase_all(T v) {
    if (v < 0 or v > N or !count(v)) return;
    root = erase(root, v, std::numeric_limits<SIZE_T>::max(), n - 1);
  }
  SIZE_T count(node* at, T a, T b, T l, T r, char i) const {
    if (!at or b < l or r < a) return 0;
    if (a <= l and r <= b) return at->cnt;
    T m = l + (r - l) / 2;
    if (at->d < i) {
      if ((at->v >> i & 1) == 0)
        return count(at, a, b, l, m, i - 1);
      else
        return count(at, a, b, m + 1, r, i - 1);
    }
    return count(at->ch[0], a, b, l, m, i - 1) +
           count(at->ch[1], a, b, m + 1, r, i - 1);
  }
  SIZE_T count(T v) const { return count(root, v, v, 0, N, n - 1); }
  SIZE_T order_of_key(T v) { return count(root, 0, v - 1, 0, N, n - 1); }
  SIZE_T lower_bound(T v) { return order_of_key(v); }
  const T operator[](SIZE_T k) const {
    node* at = root;
    T l = 0, r = N;
    char i = n - 1;
    while (l < r) {
      T m = l + (r - l) / 2;
      if (at->d < i) {
        if ((at->v >> i & 1) == 0)
          r = m;
        else
          l = m + 1;
        i--;
        continue;
      }
      if (count(at->ch[0]) > k)
        at = at->ch[0], r = m;
      else {
        k -= count(at->ch[0]);
        at = at->ch[1];
        l = m + 1;
      }
      i--;
    }
    return l;
  }
  node* merge(node* l, node* r, char i) {
    if (!l or !r) return l ? l : r;
    cut(l, r->v, i, r), cut(r, l->v, i, l);
    if (l->d == -1) {
      if (MULTI) l->cnt += r->cnt;
      delete r;
      return l;
    }
    for (int j = 0; j < 2; j++) l->ch[j] = merge(l->ch[j], r->ch[j], l->d - 1);
    l->update(), delete r;
    return l;
  }
  void merge(sms_mo& second) {
    if (N > second.N) swap(*this, second);
    expand(second.N);
    root = merge(root, second.root, n - 1);
    second.root = NULL;
  }
  node* split(node*& x, SIZE_T k) {
    if (k <= 0 or !x) return NULL;
    node* ret = new node(x);
    ret->ch[0] = ret->ch[1] = NULL;
    ret->cnt = 0;
    if (x->d == -1)
      x->cnt -= k, ret->cnt += k, ret->mi = x->mi;
    else {
      if (k <= count(x->ch[0]))
        ret->ch[0] = split(x->ch[0], k);
      else {
        ret->ch[1] = split(x->ch[1], k - count(x->ch[0]));
        std::swap(x->ch[0], ret->ch[0]);
      }
      ret->update(), x->update();
    }
    if (!x->cnt) delete x, x = NULL;
    return ret;
  }
  void split(SIZE_T k, sms_mo& second) {
    second.clear();
    second.root = split(root, std::min(k, size()));
    second.N = N, second.n = n;
  }
  void split_val(T k, sms_mo& second) { split(order_of_key(k), second); }
  T min() { return root->mi; };
};
vector<int> ans;
int n;
void rec(sms_mo<int>::node* at, int c) {
  if (!at) return;
  if (at->d == -1) return void(ans[at->v] = c);
  rec(at->ch[0], c), rec(at->ch[1], c);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  vector<sms_mo<int>> v(101, sms_mo<int>(n));
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    v[x].insert(i);
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r, x, y;
    cin >> l >> r >> x >> y;
    l--, r--;
    if (x == y) continue;
    sms_mo<int> L, M;
    v[x].split_val(r + 1, M);
    M.split_val(l, L);
    v[x].merge(L);
    v[y].merge(M);
  }
  ans.resize(n);
  for (int i = 0; i < 101; i++) rec(v[i].root, i);
  for (int i : ans) cout << i << " ";
  cout << '\n';
  return 0;
}
