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 = 2e5 + 2;
const int M = 2e6 + 2;
const int mod = 998244353;
const int inf = 2e9 + 3;
const long long INF = 1e16;
int n, q, ans[N];
struct node {
  node *l, *r;
  int x, y;
  node(int nval) {
    x = nval;
    y = (rand() << 16) | rand();
    l = r = nullptr;
  }
} * t[101];
void init() {
  for (int i = 1; i <= 100; ++i) t[i] = nullptr;
}
node *merge(node *t1, node *t2) {
  if (!t1) return t2;
  if (!t2) return t1;
  if (t1->y > t2->y) {
    t1->r = merge(t1->r, t2);
    return t1;
  } else {
    t2->l = merge(t1, t2->l);
    return t2;
  }
}
pair<node *, node *> split(node *t, int k) {
  if (!t) return {nullptr, nullptr};
  if (k >= t->x) {
    pair<node *, node *> cnt = split(t->r, k);
    t->r = cnt.first;
    return {t, cnt.second};
  } else {
    pair<node *, node *> cnt = split(t->l, k);
    t->l = cnt.second;
    return {cnt.first, t};
  }
}
node *unite(node *t1, node *t2) {
  if (!t1) return t2;
  if (!t2) return t1;
  if (t1->y > t2->y) {
    pair<node *, node *> cnt = split(t2, t1->x);
    t1->r = unite(t1->r, cnt.second);
    t1->l = unite(t1->l, cnt.first);
    return t1;
  } else {
    pair<node *, node *> cnt = split(t1, t2->x);
    t2->r = unite(t2->r, cnt.second);
    t2->l = unite(t2->l, cnt.first);
    return t2;
  }
}
void dfs(node *v, int i) {
  if (!v) return;
  ans[v->x] = i;
  dfs(v->l, i);
  dfs(v->r, i);
}
void out(node *v) {
  if (!v) return;
  out(v->l);
  cerr << v->x << " ";
  out(v->r);
}
int main() {
  init();
  scanf("%d", &n);
  for (int i = 1, x; i <= n; ++i) {
    scanf("%d", &x);
    t[x] = merge(t[x], new node(i));
  }
  scanf("%d", &q);
  while (q--) {
    int l, r, x, y;
    scanf("%d %d %d %d", &l, &r, &x, &y);
    if (x == y) continue;
    pair<node *, node *> R = split(t[x], r);
    pair<node *, node *> L = split(R.first, l - 1);
    t[x] = merge(L.first, R.second);
    t[y] = unite(L.second, t[y]);
  }
  for (int i = 1; i <= 100; ++i) dfs(t[i], i);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
}
