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("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
const int maxn = 200000;
const int oo = UINT_MAX;
const int mod = 1e9 + 7;
short lz[maxn * 4 + 5][102];
short a[maxn + 5];
void build(int v, int tl, int tr) {
  for (int i = 1; i <= 100; i++) lz[v][i] = i;
  if (tl == tr) return;
  int tm = (tl + tr) / 2;
  build(v * 2, tl, tm);
  build(v * 2 + 1, tm + 1, tr);
}
void update(int v, int tl, int tr, int l, int r, short oval, short nval) {
  if (tl != tr) {
    for (short j = 1; j <= 100; ++j) {
      lz[v * 2][j] = lz[v][lz[v * 2][j]];
      lz[v * 2 + 1][j] = lz[v][lz[v * 2 + 1][j]];
    }
    for (short i = 1; i <= 100; ++i) lz[v][i] = i;
  }
  if (l > r) return;
  if (tl >= l && tr <= r) {
    for (short j = 1; j <= 100; ++j) {
      if (lz[v][j] == oval) lz[v][j] = nval;
    }
    return;
  }
  int tm = (tl + tr) / 2;
  update(v * 2, tl, tm, l, min(tm, r), oval, nval);
  update(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r, oval, nval);
}
short answer(int v, int tl, int tr, int pos, short val) {
  if (tl != tr) {
    for (short j = 1; j <= 100; ++j) {
      lz[v * 2][j] = lz[v][lz[v * 2][j]];
      lz[v * 2 + 1][j] = lz[v][lz[v * 2 + 1][j]];
    }
    for (short i = 1; i <= 100; ++i) lz[v][i] = i;
  }
  if (tl == tr) return lz[v][val];
  int tm = (tl + tr) / 2;
  if (pos <= tm)
    return answer(v * 2, tl, tm, pos, val);
  else
    return answer(v * 2 + 1, tm + 1, tr, pos, val);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  build(1, 1, n);
  for (int i = 1; i <= n; ++i) cin >> a[i];
  int t;
  cin >> t;
  while (t--) {
    int l, r;
    short oval, nval;
    cin >> l >> r >> oval >> nval;
    update(1, 1, n, l, r, oval, nval);
  }
  for (int i = 1; i <= n; ++i) cout << answer(1, 1, n, i, a[i]) << " ";
}
