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;
template <typename T>
void out(T x) {
  cout << x << endl;
  exit(0);
}
using ll = long long;
const int maxn = 1e6 + 5;
int n;
struct query {
  int t, x, y;
  query(int _t, int _x, int _y) : t(_t), x(_x), y(_y) {}
};
vector<query> ev[maxn];
int a[maxn];
vector<int> t[maxn];
void build(int v, int tl, int tr) {
  for (int i = 0; i <= 100; i++) {
    t[v].push_back(i);
  }
  if (tl != tr) {
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
  }
}
void upd(int v, int tl, int tr, query Q) {
  if (tl == tr) {
    t[v][Q.x] = Q.y;
  } else {
    int tm = (tl + tr) / 2;
    if (tl <= Q.t && Q.t <= tm) {
      upd(2 * v, tl, tm, Q);
    } else {
      upd(2 * v + 1, tm + 1, tr, Q);
    }
    for (int i = 0; i <= 100; i++) {
      t[v][i] = t[2 * v + 1][t[2 * v][i]];
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int q;
  cin >> q;
  build(1, 1, q);
  for (int i = 1; i <= q; i++) {
    int l, r, x, y;
    cin >> l >> r >> x >> y;
    ev[l].push_back({i, x, y});
    ev[r + 1].push_back({i, x, x});
  }
  for (int i = 1; i <= n; i++) {
    for (auto e : ev[i]) {
      upd(1, 1, q, e);
    }
    int cur = t[1][a[i]];
    cout << cur << " ";
  }
  cout << endl;
  return 0;
}
