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 Query {
  int l, r;
  short int x, y;
  Query() {}
  void setQuery(int ll, int rr, int xx, int yy) {
    l = ll;
    r = rr;
    x = xx;
    y = yy;
  }
};
struct Node {
  short int val;
  bool v[101];
  Node() {}
};
int indexes[101][200004];
int indexesSize[101];
int a[200001];
Query qs[200000];
const int treeSize = 1 << 18;
const int treeSize2 = treeSize << 1;
Node tree[treeSize2];
int xx, yy;
void update(int p, int l, int r, int ql, int qr) {
  int m = (l + r) >> 1, pp = (p << 1);
  if (tree[p].val) {
    if (ql == l && qr == r) {
      tree[p].v[xx] = 0;
      tree[p].v[yy] = 1;
      tree[p].val = yy;
      bool f1 = 1, f2 = 1;
      do {
        pp = p;
        p >>= 1;
        tree[p].v[yy] = 1;
        if (f1) {
          if (!tree[pp ^ 1].v[xx])
            tree[p].v[xx] = 0;
          else
            f1 = 0;
        }
        if (f2) {
          if (tree[pp ^ 1].val ^ tree[pp].val)
            f2 = 0;
          else {
            tree[p].val = yy;
            tree[pp].v[yy] = tree[pp ^ 1].v[yy] = 0;
          }
        }
        if (!(p > 1 && (f1 | f2))) break;
        pp = p;
        p >>= 1;
        tree[p].v[yy] = 1;
        if (f1) {
          if (!tree[pp ^ 1].v[xx])
            tree[p].v[xx] = 0;
          else
            f1 = 0;
        }
        if (f2) {
          if (tree[pp ^ 1].val ^ tree[pp].val)
            f2 = 0;
          else {
            tree[p].val = yy;
            tree[pp].v[yy] = tree[pp ^ 1].v[yy] = 0;
          }
        }
        if (!(p > 1 && (f1 | f2))) break;
        pp = p;
        p >>= 1;
        tree[p].v[yy] = 1;
        if (f1) {
          if (!tree[pp ^ 1].v[xx])
            tree[p].v[xx] = 0;
          else
            f1 = 0;
        }
        if (f2) {
          if (tree[pp ^ 1].val ^ tree[pp].val)
            f2 = 0;
          else {
            tree[p].val = yy;
            tree[pp].v[yy] = tree[pp ^ 1].v[yy] = 0;
          }
        }
      } while (p > 1 && (f1 | f2));
      p >>= 1;
      while (p && !tree[p].v[yy]) {
        tree[p].v[yy] = 1;
        p >>= 1;
      }
      return;
    }
    tree[pp].val = tree[pp ^ 1].val = tree[p].val;
    tree[pp].v[tree[p].val] = tree[pp ^ 1].v[tree[p].val] = 1;
    tree[p].val = 0;
  }
  if (ql <= m && tree[pp].v[xx]) update(pp, l, m, ql, min(m, qr));
  if (qr > m && tree[++pp].v[xx]) update(pp, m + 1, r, max(ql, m + 1), qr);
  return;
}
int rp[101][200001] = {0};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  cin >> n;
  int good[100] = {0};
  int goodSize = 0;
  for (int i = 1, ai; i <= n; i++) {
    cin >> ai;
    a[i] = ai;
    indexes[ai][indexesSize[ai]++] = i;
    rp[ai][i] = 1;
  }
  for (int i = 1; i <= 100; i++) {
    if (indexesSize[i]) {
      good[goodSize++] = i;
    }
  }
  for (int i = 1; i <= 100; i++) {
    for (int j = 1; j <= n; j++) rp[i][j] += rp[i][j - 1];
  }
  int q, l, r, x, y;
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> l >> r >> x >> y;
    qs[i].setQuery(l, r, x, y);
  }
  for (int ii = 0; ii < goodSize; ii++) {
    int i = good[ii];
    int iSize = indexesSize[i], inn = 1;
    while (iSize) {
      iSize >>= 1;
      inn <<= 1;
    }
    memset(tree, 0, sizeof(Node) * (inn << 1));
    tree[1].v[i] = (tree[1].val = i);
    int m = (1 + inn) >> 1;
    for (int j = 0; j < q; j++) {
      Query qu = qs[j];
      l = rp[i][qu.l] + !(rp[i][qu.l] - rp[i][qu.l - 1]);
      r = rp[i][qu.r];
      xx = qu.x;
      yy = qu.y;
      if (l <= r && tree[1].v[qu.x] && xx != yy) {
        if (tree[1].val) {
          tree[2].val = tree[3].val = tree[1].val;
          tree[2].v[tree[1].val] = tree[3].v[tree[1].val] = 1;
          tree[1].val = 0;
        }
        if (l <= m && tree[2].v[qu.x]) update(2, 1, m, l, min(m, r));
        if (r > m && tree[3].v[qu.x]) update(3, m + 1, inn, max(l, m + 1), r);
      }
    }
    for (int j = 0; j < indexesSize[i]; j += 2) {
      l = 1, r = inn;
      int p = 1, ql = j + 1;
      do {
        m = (l + r) >> 1;
        int pp = p << 1;
        if (tree[p].val) {
          tree[pp].val = tree[pp + 1].val = tree[p].val;
          tree[p].val = 0;
        }
        p = pp;
        if (ql <= m)
          r = m;
        else
          p++, l = m + 1;
        if (!(l ^ r)) break;
        m = (l + r) >> 1, pp = p << 1;
        if (tree[p].val) {
          tree[pp].val = tree[pp + 1].val = tree[p].val;
          tree[p].val = 0;
        }
        p = pp;
        if (ql <= m)
          r = m;
        else
          p++, l = m + 1;
        if (!(l ^ r)) break;
        m = (l + r) >> 1, pp = p << 1;
        if (tree[p].val) {
          tree[pp].val = tree[pp + 1].val = tree[p].val;
          tree[p].val = 0;
        }
        p = pp;
        if (ql <= m)
          r = m;
        else
          p++, l = m + 1;
      } while (l ^ r);
      a[indexes[i][j]] = tree[p].val;
      a[indexes[i][ql]] = tree[(++p)++].val;
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << ' ';
  }
  cout << '\n';
  flush(cout);
  return 0;
}
