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 N = 200002, M = 102;
int n, q, a[N];
struct item {
  int key, prior;
  item *l, *r;
  item() {}
  item(int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) {}
};
typedef item* pitem;
pitem roots[M];
void split(pitem t, int key, pitem& l, pitem& r) {
  if (!t)
    l = r = NULL;
  else if (key < t->key)
    split(t->l, key, l, t->l), r = t;
  else
    split(t->r, key, t->r, r), l = t;
}
void insert(pitem& t, pitem it) {
  if (!t)
    t = it;
  else if (it->prior > t->prior)
    split(t, it->key, it->l, it->r), t = it;
  else
    insert(it->key < t->key ? t->l : t->r, it);
}
void merge(pitem& t, pitem l, pitem r) {
  if (!l || !r)
    t = l ? l : r;
  else if (l->prior > r->prior)
    merge(l->r, l->r, r), t = l;
  else
    merge(r->l, l, r->l), t = r;
}
pitem unite(pitem l, pitem r) {
  if (!l || !r) return l ? l : r;
  if (l->prior < r->prior) swap(l, r);
  pitem lt, rt;
  split(r, l->key, lt, rt);
  l->l = unite(l->l, lt);
  l->r = unite(l->r, rt);
  return l;
}
void dfs(pitem x, int v) {
  if (!x) return;
  a[x->key] = v;
  dfs(x->l, v);
  dfs(x->r, v);
}
int main() {
  srand(time(NULL));
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    insert(roots[a[i]], new item(i, rand()));
  }
  scanf("%d", &q);
  while (q--) {
    int l, r, x, y;
    scanf("%d %d %d %d", &l, &r, &x, &y);
    pitem a, b, c, d;
    split(roots[x], l - 1, a, b);
    split(b, r, c, d);
    merge(roots[x], a, d);
    roots[y] = unite(roots[y], c);
  }
  for (int i = 1; i <= M - 1; ++i) dfs(roots[i], i);
  for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
}
