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;
const long long maxn = 2e5 + 500;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 500;
char seg[maxn * 4][101];
char a[maxn];
void f(long long a) {
  for (char j = 1; j <= 100; j++) {
    seg[a][j] = j;
  }
}
void shift(long long a) {
  long long lb = 2 * a;
  long long rb = 2 * a + 1;
  for (char i = 1; i <= 100; i++) {
    seg[lb][i] = seg[a][seg[lb][i]];
    seg[rb][i] = seg[a][seg[rb][i]];
  }
  f(a);
}
void update(long long L, long long R, long long node, long long l, long long r,
            char x, char y) {
  if (l <= L && R <= r) {
    for (char i = 1; i <= 100; i++) {
      if (seg[node][i] == x) {
        seg[node][i] = y;
      }
    }
    return;
  }
  if (R <= l || r <= L) {
    return;
  }
  long long mid = (L + R) / 2;
  shift(node);
  update(L, mid, 2 * node, l, r, x, y);
  update(mid, R, 2 * node + 1, l, r, x, y);
}
vector<long long> ans;
void bild(long long l, long long r, long long node) {
  if (l + 1 == r) {
    ans.push_back(seg[node][a[l]]);
    return;
  }
  shift(node);
  long long mid = (l + r) / 2;
  bild(l, mid, 2 * node);
  bild(mid, r, 2 * node + 1);
}
int main() {
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    long long v;
    cin >> v;
    a[i] = v;
  }
  for (long long i = 0; i < 4 * maxn; i++) {
    f(i);
  }
  long long q;
  cin >> q;
  for (long long i = 0; i < q; i++) {
    long long l, r, x, y;
    cin >> l >> r >> x >> y;
    l--;
    r--;
    update(0, n, 1, l, r + 1, x, y);
  }
  bild(0, n, 1);
  for (long long i = 0; i < n; i++) {
    cout << ans[i] << ' ';
  }
}
