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 maxn = 1e7 + 7;
int root[101];
int ls[maxn], rs[maxn], tot = 0;
int res[maxn];
int Merge(int u, int v, int l, int r) {
  if (!u || !v) return u | v;
  if (l == r) {
    return u;
  }
  int md = l + r >> 1;
  ls[u] = Merge(ls[u], ls[v], l, md);
  rs[u] = Merge(rs[u], rs[v], md + 1, r);
  return u;
}
void Run(int& rx, int& ry, int l, int r, int L, int R) {
  if (!rx) return;
  if (!ry) {
    ry = ++tot;
  }
  int md = l + r >> 1;
  if (l == L && r == R) {
    ry = Merge(rx, ry, l, r);
    rx = 0;
    return;
  } else {
    if (R <= md)
      Run(ls[rx], ls[ry], l, md, L, R);
    else if (L >= md + 1)
      Run(rs[rx], rs[ry], md + 1, r, L, R);
    else {
      Run(ls[rx], ls[ry], l, md, L, md);
      Run(rs[rx], rs[ry], md + 1, r, md + 1, R);
    }
  }
}
void query(int rt, int l, int r, int v) {
  if (!rt) return;
  if (l == r) {
    res[l] = v;
    return;
  }
  int md = l + r >> 1;
  query(ls[rt], l, md, v);
  query(rs[rt], md + 1, r, v);
}
void ins(int& rt, int l, int r, int pos) {
  if (!rt) {
    rt = ++tot;
  }
  if (l == r) {
    return;
  }
  int md = l + r >> 1;
  if (pos <= md)
    ins(ls[rt], l, md, pos);
  else {
    ins(rs[rt], md + 1, r, pos);
  }
}
int n;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    ins(root[x], 1, n, i);
  }
  int m;
  scanf("%d", &m);
  while (m--) {
    int l, r, x, y;
    scanf("%d %d %d %d", &l, &r, &x, &y);
    if (x == y) continue;
    Run(root[x], root[y], 1, n, l, r);
  }
  for (int i = 1; i <= 100; ++i) {
    query(root[i], 1, n, i);
  }
  for (int i = 1; i <= n; ++i) printf("%d%c", res[i], i == n ? '\n' : ' ');
  return 0;
}
