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;
int n, x, m, l, r, y;
vector<pair<int, int> > ans;
inline int myrand() { return rand() ^ (rand() << 15); }
struct item {
  item *l, *r;
  int key, prior;
  item() {}
  item(int x) {
    key = x;
    prior = myrand();
    l = r = nullptr;
  }
};
typedef item *pitem;
pitem t[101], a, b, c, d;
void Merge(pitem &v, pitem l, pitem r) {
  if (!l || !r) {
    v = l ? l : r;
  } else if (l->prior > r->prior) {
    Merge(l->r, l->r, r);
    v = l;
  } else {
    Merge(r->l, l, r->l);
    v = r;
  }
}
void Split(pitem v, int key, pitem &l, pitem &r) {
  if (!v) {
    l = r = nullptr;
    return;
  }
  if (key < v->key) {
    Split(v->l, key, l, v->l);
    r = v;
  } else {
    Split(v->r, key, v->r, r);
    l = v;
  }
}
pitem Unite(pitem l, pitem r) {
  if (!l || !r) {
    return l ? l : r;
  }
  if (l->prior < r->prior) {
    swap(l, r);
  }
  pitem tl, tr;
  Split(r, l->key, tl, tr);
  l->l = Unite(l->l, tl);
  l->r = Unite(l->r, tr);
  return l;
}
void dfs(pitem v) {
  if (!v) {
    return;
  }
  dfs(v->l);
  ans.push_back(make_pair(v->key, x));
  dfs(v->r);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  srand(time(nullptr));
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    Merge(t[x], t[x], new item(i));
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    cin >> l >> r >> x >> y;
    if (x == y) {
      continue;
    }
    Split(t[x], l - 1, t[x], a);
    Split(a, r, a, b);
    Merge(t[x], t[x], b);
    Split(t[y], l - 1, t[y], c);
    Split(c, r, c, d);
    c = Unite(c, a);
    Merge(t[y], t[y], c);
    Merge(t[y], t[y], d);
  }
  for (int i = 1; i <= 100; i++) {
    x = i;
    dfs(t[i]);
  }
  sort(ans.begin(), ans.end());
  for (auto it : ans) {
    cout << it.second << " ";
  }
}
