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 = 4e5 + 3;
int rt[101], rub[maxn << 5], top;
struct SegmenTree {
  int lson, rson, sum;
};
SegmenTree tree[maxn << 2];
int read() {
  int ret = 0, f = 1;
  char x = getchar();
  while (!isdigit(x)) {
    if (x == '-') f = -1;
    x = getchar();
  }
  while (isdigit(x)) {
    ret = ret * 10 + x - '0';
    x = getchar();
  }
  return ret * f;
}
int lson[maxn << 5], rson[maxn << 5], sum[maxn << 5], cnt, n;
int newnode() { return top ? rub[top--] : ++cnt; }
void delnode(int &x) {
  lson[x] = rson[x] = sum[x] = 0;
  rub[++top] = x;
  x = 0;
}
void pushup(int p) { sum[p] = sum[lson[p]] + sum[rson[p]]; }
void Modify(int &p, int x, int l, int r) {
  if (!p) p = newnode();
  if (l == r) {
    sum[p] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    Modify(lson[p], x, l, mid);
  else
    Modify(rson[p], x, mid + 1, r);
  pushup(p);
}
void merge(int &x, int &y, int l, int r) {
  if (!x || !y) {
    x += y;
    return;
  }
  if (l == r) {
    sum[x] += sum[y];
    delnode(y);
  }
  int mid = (l + r) >> 1;
  merge(lson[x], lson[y], l, mid);
  merge(rson[x], rson[y], mid + 1, r);
  delnode(y);
  pushup(x);
}
void split(int &x, int &y, int ql, int qr, int l, int r) {
  if (!y) return;
  if (ql <= l && r <= qr) {
    x = y;
    y = 0;
    return;
  }
  if (!x) x = newnode();
  int mid = (l + r) >> 1;
  if (ql <= mid) split(lson[x], lson[y], ql, qr, l, mid);
  if (qr > mid) split(rson[x], rson[y], ql, qr, mid + 1, r);
  pushup(x);
  pushup(y);
}
int a[maxn];
void dfs(int p, int clr, int l, int r) {
  if (l == r) {
    a[l] = (sum[p] ? clr : a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  dfs(lson[p], clr, l, mid);
  dfs(rson[p], clr, mid + 1, r);
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    Modify(rt[a[i]], i, 1, n);
  }
  int Q = read();
  while (Q--) {
    int l = read(), r = read(), x = read(), y = read();
    if (x != y) {
      int tmp = 0;
      split(tmp, rt[x], l, r, 1, n);
      merge(rt[y], tmp, 1, n);
    }
  }
  for (int i = 1; i <= 100; i++) dfs(rt[i], i, 1, n);
  for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
}
