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 N = 2e5 + 5;
int n, m, l, r, x, y, cur;
vector<pair<int, int> > ans;
struct item {
  item *l, *r;
  int sum;
  item() {
    sum = 0;
    l = r = nullptr;
  }
};
typedef item *pitem;
pitem t[105];
void update(pitem &v, int l, int r, int pos) {
  if (!v) {
    v = new item();
  }
  v->sum++;
  if (l == r) {
    return;
  }
  int mid = (r + l) >> 1;
  if (pos <= mid) {
    update(v->l, l, mid, pos);
  } else {
    update(v->r, mid + 1, r, pos);
  }
}
inline int sum(pitem v) { return v ? v->sum : 0; }
void merging(pitem &v1, pitem &v2, int l, int r, int tl, int tr) {
  if (!v1 || l > r || l > tr || tl > r) {
    return;
  }
  if (tl <= l && r <= tr && !v2) {
    v2 = v1;
    v1 = nullptr;
    return;
  }
  if (!v2) {
    v2 = new item();
  }
  int mid = (r + l) >> 1;
  merging(v1->l, v2->l, l, mid, tl, tr);
  merging(v1->r, v2->r, mid + 1, r, tl, tr);
  v2->sum = sum(v2->l) + sum(v2->r);
  v1->sum = sum(v1->l) + sum(v1->r);
  if (!v1->sum) {
    v1 = nullptr;
  }
}
void dfs(pitem v, int l, int r) {
  if (!v) {
    return;
  }
  if (l == r) {
    ans.push_back(make_pair(l, cur));
    return;
  }
  int mid = (r + l) >> 1;
  dfs(v->l, l, mid);
  dfs(v->r, mid + 1, r);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    update(t[x], 1, n, i);
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    cin >> l >> r >> x >> y;
    if (x == y) {
      continue;
    }
    merging(t[x], t[y], 1, n, l, r);
  }
  for (int i = 1; i <= 100; i++) {
    cur = i;
    dfs(t[i], 1, n);
  }
  sort(ans.begin(), ans.end());
  for (auto it : ans) {
    cout << it.second << " ";
  }
}
