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")
using namespace std;
const long long inf = 1e18;
const long long mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long powm(long long a, long long b, long long m);
short hola[600000][101];
void pushdown(long long seg) {
  for (long long i = 1; i <= 100; i++) {
    hola[seg << 1][i] = hola[seg][hola[seg << 1][i]];
    hola[seg << 1 | 1][i] = hola[seg][hola[seg << 1 | 1][i]];
  }
  for (long long i = 1; i <= 100; i++) hola[seg][i] = i;
}
void query(long long seg, long long lb, long long rb, long long l, long long r,
           long long fr, long long to) {
  if (rb < l || lb > r) return;
  if (l <= lb && r >= rb) {
    for (long long i = 1; i <= 100; i++)
      if (hola[seg][i] == fr) hola[seg][i] = to;
    return;
  }
  pushdown(seg);
  query(seg << 1, lb, (lb + rb) >> 1, l, r, fr, to);
  query(seg << 1 | 1, ((lb + rb) >> 1) + 1, rb, l, r, fr, to);
}
short a[200001];
void pushpush(long long seg, long long lb, long long rb) {
  if (lb != rb) {
    pushdown(seg);
    pushpush(seg << 1, lb, (lb + rb) >> 1);
    pushpush(seg << 1 | 1, ((lb + rb) >> 1) + 1, rb);
  } else
    a[lb] = hola[seg][a[lb]];
}
void solve() {
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i < 524288; i++)
    for (long long j = 1; j <= 100; j++) hola[i][j] = j;
  long long q;
  cin >> q;
  long long l, r, x, y;
  while (q--) {
    cin >> l >> r >> x >> y;
    query(1, 1, n, l, r, x, y);
  }
  pushpush(1, 1, n);
  for (long long i = 1; i <= n; i++) cout << a[i] << " ";
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  srand(chrono::steady_clock::now().time_since_epoch().count());
  clock_t clk = clock();
  long long t = 1;
  while (t--) solve();
  clk = clock() - clk;
  fflush(stdout);
  return 0;
}
long long powm(long long a, long long b, long long m) {
  long long te = 1;
  while (b) {
    if (b & 1) te = (te * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return te;
}
