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;
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long a, long long b, long long m) {
  if (b == 0LL) return 1LL;
  if (b == 1LL) return mod(a, m);
  long long k = mod(exp(a, b / 2, m), m);
  if (b & 1LL) {
    return mod(a * mod(k * k, m), m);
  } else
    return mod(k * k, m);
}
const int N = 200100;
int a[N];
struct node {
  vector<int> f;
  node *l, *r;
  int L, R;
  node(int le, int ri) {
    L = le, R = ri;
    f = vector<int>(101, 0);
    for (int i = 1; i < (101); ++i) f[i] = i;
    if (L != R) {
      int m = (L + R) >> 1;
      l = new node(L, m);
      r = new node(m + 1, R);
    }
  }
  void apply(const vector<int>& g) {
    for (int i = 1; i < (101); ++i) f[i] = g[f[i]];
  }
  void apply(int x, int y) {
    for (int i = 1; i < (101); ++i) {
      if (f[i] == x) f[i] = y;
    }
  }
  void zera() {
    for (int i = 1; i < (101); ++i) {
      f[i] = i;
    }
  }
  void upd(int a, int b, int x, int y) {
    if (L > b or R < a) return;
    if (a <= L and R <= b) {
      apply(x, y);
      return;
    }
    l->apply(f);
    r->apply(f);
    zera();
    l->upd(a, b, x, y);
    r->upd(a, b, x, y);
  }
  void compute_answer() {
    if (L == R) {
      cout << f[a[L]] << " ";
      return;
    }
    l->apply(f);
    r->apply(f);
    l->compute_answer();
    r->compute_answer();
  }
};
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  node* tree = new node(1, n);
  int q;
  cin >> q;
  while (q--) {
    int l, r, x, y;
    cin >> l >> r >> x >> y;
    tree->upd(l, r, x, y);
  }
  tree->compute_answer();
}
