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 <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
template <class T, class... U>
void DEBUG(const T &head, const U &...tail) {}
int MOD = 1e9 + 7;
void ADD(int64_t &x, int64_t v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
const int SIZE = 1e6 + 10;
unsigned long long a[100][3200];
unsigned long long pre[64], pro[64];
unsigned long long mask;
int main() {
  for (int i = 0; i < (64); ++i) {
    mask |= 1ULL << i;
    pre[i] = 1ULL << i;
    if (i) pre[i] |= pre[i - 1];
  }
  for (int i = 63; i >= 0; i--) {
    pro[i] = 1ULL << i;
    if (i != 63) pro[i] |= pro[i + 1];
  }
  int n;
  R(n);
  for (int i = 0; i < (n); ++i) {
    int x;
    R(x);
    x--;
    a[x][i / 64] |= 1ULL << i % 64;
  }
  int q;
  R(q);
  while (q--) {
    int l, r, x, y;
    R(l, r, x, y);
    if (x == y) continue;
    l--;
    r--;
    x--;
    y--;
    int lid = l >> 6;
    int rid = r >> 6;
    if (lid == rid) {
      unsigned long long v = pre[r & 63] & pro[l & 63];
      a[y][lid] |= v & a[x][lid];
      a[x][lid] &= mask ^ v;
      continue;
    }
    for (int i = (lid + 1); i < (rid); ++i) {
      a[y][i] |= a[x][i];
      a[x][i] = 0;
    }
    a[y][lid] |= pro[l & 63] & a[x][lid];
    if (l & 63)
      a[x][lid] &= pre[(l & 63) - 1];
    else
      a[x][lid] = 0;
    a[y][rid] |= pre[r & 63] & a[x][rid];
    if ((r & 63) != 63)
      a[x][rid] &= pro[(r & 63) + 1];
    else
      a[x][rid] = 0;
  }
  vector<int> an;
  for (int i = 0; i < (n); ++i) {
    for (int j = 0; j < (100); ++j)
      if ((a[j][i / 64] >> i % 64) & 1) {
        an.push_back(j + 1);
        break;
      }
  }
  W(an);
  return 0;
}
