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 int maxn = 200010, pow2 = 1 << 18;
int n, a[pow2];
int prop[pow2 << 1][101];
bool p[pow2 << 1];
void propagate(int t) {
  p[t] = false;
  p[2 * t] = true;
  p[2 * t + 1] = true;
  for (int i = 1; i <= 100; i++) {
    prop[2 * t][i] = prop[t][prop[2 * t][i]];
    prop[2 * t + 1][i] = prop[t][prop[2 * t + 1][i]];
  }
  for (int i = 1; i <= 100; i++) prop[t][i] = i;
}
void propagate_end(int t, int x, int y) {
  a[t] = prop[t + pow2][a[t]];
  if (a[t] == x) a[t] = y;
  for (int i = 1; i <= 100; i++) prop[t + pow2][i] = i;
}
void update(int t, int lt, int rt, int l, int r, int x, int y) {
  if (rt < l || lt > r) return;
  if (t >= pow2) {
    propagate_end(t - pow2, x, y);
    return;
  }
  if (p[t]) propagate(t);
  if (lt >= l && rt <= r) {
    prop[t][x] = y;
    propagate(t);
  } else {
    update(2 * t, lt, (lt + rt) / 2, l, r, x, y);
    update(2 * t + 1, (lt + rt + 1) / 2, rt, l, r, x, y);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  for (int i = 1; i < (pow2 << 1); i++)
    for (int j = 1; j <= 100; j++) prop[i][j] = j;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  int q, l, r, x, y;
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> l >> r >> x >> y;
    l--;
    r--;
    update(1, 0, pow2 - 1, l, r, x, y);
  }
  for (int i = 1; i < pow2; i++)
    if (p[i]) propagate(i);
  for (int i = 0; i < pow2; i++) propagate_end(i, 1, 1);
  for (int i = 0; i < n; i++) cout << a[i] << " ";
  return 0;
}
