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>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
using namespace std;
function<void(void)> ____ = []() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
};
template <typename T>
vector<T> &operator<<(vector<T> &__container, T x) {
  __container.push_back(x);
  return __container;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &__container) {
  for (T _ : __container) out << _ << ' ';
  return out;
}
const int MAXN = (1 << 18) + 7;
const int MAXV = 101;
struct SegmentTree {
  int l[MAXN << 1], r[MAXN << 1];
  int f[MAXN << 1][MAXV];
  void build(int L, int R, int rt = 1) {
    l[rt] = L;
    r[rt] = R;
    for (int i = 1; i < MAXV; i++) f[rt][i] = i;
    if (L + 1 == R) return;
    int mid = (L + R) >> 1;
    build(L, mid, rt << 1);
    build(mid, R, rt << 1 | 1);
  }
  void pushdown(int rt) {
    for (int i = 1; i < MAXV; i++) {
      f[rt << 1][i] = f[rt][f[rt << 1][i]];
      f[rt << 1 | 1][i] = f[rt][f[rt << 1 | 1][i]];
    }
    for (int i = 1; i < MAXV; i++) f[rt][i] = i;
  }
  void modify(int L, int R, int x, int y, int rt = 1) {
    if (L >= r[rt] or l[rt] >= R) return;
    if (L <= l[rt] and r[rt] <= R) {
      for (int i = 1; i < MAXV; i++)
        if (f[rt][i] == x) f[rt][i] = y;
      return;
    }
    pushdown(rt);
    modify(L, R, x, y, rt << 1);
    modify(L, R, x, y, rt << 1 | 1);
  }
  void print(vector<int> &A, int rt = 1) {
    if (l[rt] + 1 == r[rt]) {
      cout << f[rt][A[l[rt]]] << ' ';
      return;
    }
    pushdown(rt);
    print(A, rt << 1);
    print(A, rt << 1 | 1);
  }
} ST;
void solve() {
  int n;
  scanf("%d", &n);
  vector<int> A(n);
  for (int &x : A) scanf("%d", &x);
  ST.build(0, n);
  int m;
  scanf("%d", &m);
  while (m--) {
    int l, r, x, y;
    scanf("%d", &l);
    scanf("%d", &r);
    scanf("%d", &x);
    scanf("%d", &y);
    l--;
    r--;
    if (x == y) continue;
    ST.modify(l, r + 1, x, y);
  }
  ST.print(A);
}
int main() {
  solve();
  return 0;
}
