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;
struct DisjointSet {
  int *p, *r, *s;
  int numDisjoint;
  DisjointSet(int N) {
    numDisjoint = N;
    r = new int[N];
    s = new int[N];
    p = new int[N];
    for (int i = 0; i < N; i++) p[i] = i;
  }
  int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  void unionSet(int i, int j) {
    if (!isSameSet(i, j)) {
      numDisjoint--;
      int x = findSet(i), y = findSet(j);
      if (r[x] > r[y]) {
        p[y] = x;
        s[x] += s[y];
      } else {
        p[x] = y;
        if (r[x] == r[y]) r[y]++;
        s[y] += s[x];
      }
    }
  }
  int sizeOfSet(int i) { return s[findSet(i)]; }
};
struct bucket {
  int *ar, *color, *whois;
  DisjointSet *dsu;
  int l, r;
  bucket(int l, int r, int *arr) {
    ar = new int[r - l + 1];
    color = new int[100];
    whois = new int[100];
    for (int i = 0; i < 100; i++) {
      color[i] = i;
    }
    for (int i = 0; i < 100; i++) whois[i] = -1;
    this->l = l;
    this->r = r;
    dsu = new DisjointSet(100);
    for (int i = 0; i < r - l + 1; i++) {
      ar[i] = arr[i + l];
      whois[ar[i]] = ar[i];
    }
  }
  void update(int L, int R, int ov, int nv) {
    if (whois[ov] == -1) return;
    if (l >= L && r <= R) {
      if (whois[nv] == -1) whois[nv] = dsu->findSet(whois[ov]);
      dsu->unionSet(whois[ov], whois[nv]);
      color[dsu->findSet(whois[ov])] = nv;
      whois[ov] = -1;
    } else if (l > R || r < L) {
      return;
    } else {
      for (int i = 0; i < 100; i++) whois[i] = -1;
      for (int i = 0; i < r - l + 1; i++) {
        ar[i] = color[dsu->findSet(ar[i])];
        if (l + i >= L && l + i <= R && ar[i] == ov) ar[i] = nv;
        whois[ar[i]] = ar[i];
      }
      dsu = new DisjointSet(100);
      for (int i = 0; i < 100; i++) {
        color[i] = i;
      }
    }
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  int *numbers = new int[n];
  for (int i = 0; i < n; i++) cin >> numbers[i], numbers[i]--;
  int sn = min(500, (int)sqrt(n)) + 10;
  int numB = n / sn;
  if (sn * numB < n) numB++;
  vector<bucket> bs;
  for (int i = 0; i < numB; i++) {
    bucket b(i * sn, min(n - 1, (i + 1) * sn - 1), numbers);
    bs.push_back(b);
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r, x, y;
    cin >> l >> r >> x >> y;
    l--;
    r--;
    x--;
    y--;
    if (x == y) continue;
    for (int j = max(0, l / sn - 1); j < numB; j++) {
      if (bs[j].l > r) break;
      bs[j].update(l, r, x, y);
    }
  }
  for (int i = 0; i < numB; i++) {
    for (int j = 0; j < bs[i].r - bs[i].l + 1; j++) {
      int v = bs[i].ar[j];
      cout << (bs[i].color[bs[i].dsu->findSet(v)] + 1) << " ";
    }
  }
}
