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 M = 102;
class SegmentTree {
  int n;
  vector<vector<int> > lazy;
  vector<bool> push;
  int left(int p) { return p << 1; }
  int right(int p) { return (p << 1) + 1; }
  int query(int p, int L, int R, int i, int x) {
    if (i > R || i < L) return -1;
    if (R == L) return lazy[p][x];
    shift(p);
    if (i >= L && i <= (L + R) / 2) {
      return query(left(p), L, (L + R) / 2, i, x);
    } else {
      return query(right(p), (L + R) / 2 + 1, R, i, x);
    }
  }

 public:
  SegmentTree(int n) {
    this->n = n;
    lazy.assign(4 * n, vector<int>(M));
    for (int i = 0; i < 4 * n; i++) {
      for (int j = 0; j < M; j++) {
        lazy[i][j] = j;
      }
    }
    push.assign(4 * n, false);
  }
  int query(int i, int x) { return query(1, 0, n - 1, i, x); }
  void upd(int id, int x, int y) {
    for (int i = 1; i <= 100; i++) {
      if (lazy[id][i] == x) lazy[id][i] = y;
    }
    push[id] = 1;
  }
  void shift(int p) {
    if (!push[p]) return;
    int l = left(p);
    int r = right(p);
    for (int i = 1; i <= 100; i++) {
      lazy[l][i] = lazy[p][lazy[l][i]];
      lazy[r][i] = lazy[p][lazy[r][i]];
    }
    for (int i = 1; i <= 100; i++) {
      lazy[p][i] = i;
    }
    push[l] = 1;
    push[r] = 1;
    push[p] = 0;
  }
  void increase(int l, int r, int v, int vv) {
    increase(l, r, v, 1, 0, n - 1, vv);
  }
  void increase(int x, int y, int v, int id, int l, int r, int vv) {
    if (x > r || y < l) return;
    if (x <= l && r <= y) {
      upd(id, v, vv);
      return;
    }
    shift(id);
    int mid = (l + r) / 2;
    increase(x, y, v, left(id), l, mid, vv);
    increase(x, y, v, right(id), mid + 1, r, vv);
  }
};
int main() {
  int n;
  scanf("%d", &n);
  vector<int> v(n);
  SegmentTree seg(n);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    v[i] = x;
  }
  int q;
  vector<pair<pair<int, int>, pair<int, int> > > queries;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int l, r, x, y;
    scanf("%d%d%d%d", &l, &r, &x, &y);
    l--, r--;
    queries.push_back({{l, r}, {x, y}});
  }
  for (auto q : queries) {
    int l = q.first.first;
    int r = q.first.second;
    int x = q.second.first;
    int y = q.second.second;
    seg.increase(l, r, x, y);
  }
  for (int i = 0; i < (int)v.size(); i++) {
    printf("%d ", seg.query(i, v[i]));
  }
  printf("\n");
  return 0;
}
